Untitled

#define MAX_S           20002
#define MAX_SCORE       300000
#define BLOCK_SIZE      200
#define NUM_BLOCK       1501
#define getHashIdx(id)  id % MAX_S
#define getScoreIdx(s)  s / BLOCK_SIZE
#define ri              register int
#define FAST            __attribute((optimize("Ofast")))         
  
struct Student {
    int id, score, grade, gender;
    Student *nextH, *preH, *nextS, *preS;
  
    Student() {}
    Student(int id, int score, int grade, int gender)
        : id(id), score(score), grade(grade), gender(gender), nextH(0), preH(0), nextS(0), preS(0) {}
  
} sArr[MAX_S], *hashTB[MAX_S], *scoreTB[2][3][NUM_BLOCK];
int sCnt;
  
FAST Student* newStudent(int id, int score, int grade, int gender) {
    sArr[sCnt] = Student(id, score, grade, gender);
    return &sArr[sCnt++];
}
  
FAST bool cmp(Student* a, Student* b) { // <
    if(a->score == b->score) return a->id < b->id;
    return a->score < b->score;
}
  
FAST void hPush(Student* s, int iH) {
    s->nextH = hashTB[iH];
    if(hashTB[iH]) {
        hashTB[iH]->preH = s;
    }
    hashTB[iH] = s;
}
  
FAST bool hFind(Student*& res, int id, int iH) {
    for(Student* s = hashTB[iH]; s; s = s->nextH) {
        if(s->id == id) {
            res = s;
            return true;
        }
    }
    return false;
}
  
FAST void hDel(Student* s, int hIdx) {
    if(hashTB[hIdx] == s) {
        hashTB[hIdx] = s->nextH;
    }
    if(s->preH) {
        s->preH->nextH = s->nextH;
    }
    if(s->nextH) {
        s->nextH->preH = s->preH;
    }
}
  
FAST void sPush(Student* s, int gender, int grade) {
    ri idx = getScoreIdx(s->score);
    if(!scoreTB[gender][grade][idx]) {
        scoreTB[gender][grade][idx] = s;
        return;
    }
 
    Student* first = scoreTB[gender][grade][idx];
    if(cmp(s, first)) {
        scoreTB[gender][grade][idx] = s;
        s->nextS = first;
        first->preS = s;
        return;
    }
  
    // s < i
    Student* mMax;
    for(Student* i = scoreTB[gender][grade][idx]; i; i = i->nextS) {
        if(cmp(s, i)) {
            s->preS = i->preS;
            if(i->preS) {
                i->preS->nextS = s;
            }
            s->nextS = i;
            i->preS = s;
            return;
        }
        mMax = i;
    }
    mMax->nextS = s;
    s->preS = mMax;
}
  
FAST void sDel(Student* s) {
    int idx = getScoreIdx(s->score);
    if(scoreTB[s->gender][s->grade][idx] == s) {
        scoreTB[s->gender][s->grade][idx] = s->nextS;
    }
    if(s->preS) {
        s->preS->nextS = s->nextS;
    }
    if(s->nextS) {
        s->nextS->preS = s->preS;
    }
}
  
FAST bool sFindHigher(Student*& res, int score, int gender, int grade) {
    ri idx = getScoreIdx(score) - 1;
    while(++idx < NUM_BLOCK && !scoreTB[gender][grade][idx]) {}
    if(idx == NUM_BLOCK) return false;
    for(Student* s = scoreTB[gender][grade][idx]; s; s = s->nextS) {
        if(s->score >= score) {
            res = s;
            return true;
        }
    }
  
    while(++idx < NUM_BLOCK && !scoreTB[gender][grade][idx]) {}
    if(idx == NUM_BLOCK) return false;
    res = scoreTB[gender][grade][idx];
  
    return true;
}
  
FAST int findHighest(int gender, int grade) {
    ri idx = NUM_BLOCK;
    while(!scoreTB[gender][grade][--idx]) {}
  
    Student* max;
    for(Student* s = scoreTB[gender][grade][idx]; s; s = s->nextS) {
        max = s;
    }
    return max->id;
}
  
FAST int findLowest(int gender, int grade) {
    ri idx = -1;
    while(++idx < NUM_BLOCK && !scoreTB[gender][grade][idx]) {}
    if(idx == NUM_BLOCK) return 0;
    return scoreTB[gender][grade][idx]->id;
}
  
FAST void init() {
    sCnt = 0;
    for(ri i = 0; i < MAX_S; i++) {
        hashTB[i] = 0;
    }
    for(ri i = 0; i < 2; i++) {
        for(ri k = 0; k < 3; k++) {
            for(ri l = 0; l < NUM_BLOCK; l++) {
                scoreTB[i][k][l] = 0;
            }
        }
    }
}
  
FAST int add(int mId, int mGrade, char mGender[7], int mScore) {
    int gender = mGender[0] != 'm';
    int grade = mGrade - 1;
    Student* s = newStudent(mId, mScore, grade, gender);
    hPush(s, getHashIdx(mId));
    sPush(s, gender, grade);
  
    return findHighest(gender, grade);
}
  
FAST int remove(int mId) {
    Student* s;
    int hIdx = getHashIdx(mId);
    if(!hFind(s, mId, hIdx)) {
        return 0;
    }
  
    hDel(s, hIdx);
    sDel(s);
    return findLowest(s->gender, s->grade);
}
  
FAST void mQuery(Student*& res, int mGradeCnt, int mGrade[], int gender, int mScore) {
    int grade;
    Student* s;
    for(ri i = 0; i < mGradeCnt; i++) {
        grade = mGrade[i] - 1;
        if(sFindHigher(s, mScore, gender, grade)) {
            if(res == 0) {
                res = s;
            } else if(cmp(s, res)) {
                res = s;
            }
        }
    }
}
  
FAST int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][7], int mScore) {
    int gender = mGender[0][0] != 'm';
    Student *res = 0;
  
    mQuery(res, mGradeCnt, mGrade, gender, mScore);
    if(mGenderCnt == 2) {
        gender = 1 - gender;
        mQuery(res, mGradeCnt, mGrade, gender, mScore);
    }
  
    if(!res) return 0;
    return res->id;
}