Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.9 kB
2
Indexable
Never
#include <set>
#include <unordered_map>
#define MXN 20001
#define REP(i,x,n) for(int i= (int)(x); i<(int)(n);++i)
#define MP make_pair
using namespace std;
typedef struct Student {
    int id;
    int grade;
    int gender;
    int score;  
}student;
int idx;
student data_base[MXN];
unordered_map<int, int> hashTable; 
set<pair<int, int>> Root[3][2]; 
  
void init() {
    idx = 0;
    hashTable.clear();
    REP(i,0,3)REP(j,0,2) Root[i][j].clear();
}
  
int add(int mId, int mGrade, char mGender[7], int mScore) {
    int gender = mGender[0] == 'm';
    data_base[++idx].id = mId;
    data_base[idx].grade= mGrade;
    data_base[idx].gender= gender;
    data_base[idx].score= mScore;
    hashTable.insert(MP(mId, idx));
    Root[mGrade - 1][gender].insert(MP(mScore, mId));
    auto it = Root[mGrade - 1][gender].end();
    return (--it)->second;
}
 
int remove(int mId) { 
    auto it = hashTable.find(mId);
    if (it == hashTable.end()) return 0;
    int id = hashTable[mId]; 
    hashTable.erase(it);  
    int grade = data_base[id].grade;
    int gender = data_base[id].gender;
    int score = data_base[id].score;
    Root[grade - 1][gender].erase(MP(score, mId));
    if (!Root[grade - 1][gender].size()) return 0;
    return Root[grade - 1][gender].begin()->second;
}
  
int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][7], int mScore) {
    int score = 3e6;
    int id = 1e9+1;
    bool ok=false;
    REP(i,0,mGradeCnt)REP(j,0,mGenderCnt){
        int grade = mGrade[i]-1;
        int gender = mGender[j][0] == 'm';
        auto it = Root[grade][gender].upper_bound(MP(mScore, -1));
        if (it == Root[grade][gender].end())
            continue;
        if (it->first < score || (it->first == score && it->second < id)) {
            score = it->first;
            id = it->second;
            ok=true;
        }
    }   
    return ok? id:0;
}