Submission #973159

#	Time	Username	Problem	Language	Result	Execution time	Memory
973159		the_coding_pooh	Examination (JOI19_examination)	C++14	100 / 100	690 ms	134120 KiB

examination

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int INF = 1e9 + 7, SIZE = 1e5 + 5, LOGC = 400;

struct event{
    int id, a, b, sum;
};

bool cmp(event e1, event e2){
    return e1.sum != e2.sum ? e1.sum > e2.sum : e1.id < e2.id;
}

vector <int> desa, desb;

int getposa(int a){
    return lower_bound(desa.begin(), desa.end(), -a) - desa.begin() + 1;
}

int getposb(int b){
    return lower_bound(desb.begin(), desb.end(), b) - desb.begin();
}

vector <event> vec;

int ptr = 0;

struct node{
    int l, r, val;
} SEGTree[SIZE * LOGC];

int BIT[2 * SIZE];

#define nd SEGTree[rt]
#define lc SEGTree[rt].l
#define rc SEGTree[rt].r

void modify_SEG(int pos, int L, int R, int rt){
    nd.val++;
    if(L == R)
        return;
    
    int M = (L + R) >> 1;
    if(pos <= M){
        if(!lc)
            lc = ++ptr;
        modify_SEG(pos, L, M, lc);
    }
    else{
        if(!rc)
            rc = ++ptr;
        modify_SEG(pos, M + 1, R, rc);
    }
    return;
}

int query_SEG(int ql, int qr, int L, int R, int rt){
    if(!rt)
        return 0;
    if(ql <= L && R <= qr)
        return nd.val;

    int M = (L + R) >> 1;

    if(qr<= M)
        return query_SEG(ql, qr, L, M, lc);
    if(ql > M)
        return query_SEG(ql, qr, M + 1, R, rc);
    return query_SEG(ql, M, L, M, lc) + query_SEG(M + 1, qr, M + 1, R, rc);
}

void modify_BIT(int posa, int posb){
    for (; posa <= desa.size(); posa += (posa &  - posa)){
        if(!BIT[posa])
            BIT[posa] = ++ptr;
        modify_SEG(posb, 0, desb.size(), BIT[posa]);
    }
    return;
}

int query_BIT(int posa, int posb){
    int ret = 0;
    for (; posa; posa -= (posa & - posa)){
        if(BIT[posa]){
            ret += query_SEG(posb, desb.size(), 0, desb.size(), BIT[posa]);
        }
    }
    return ret;
}

int N, Q;

int ans[SIZE];

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> N >> Q;

    event in_e;

    for (int i = 0; i < N; i++){
        in_e.id = 0;
        cin >> in_e.a >> in_e.b;
        in_e.sum = in_e.a + in_e.b;
        desa.push_back(-in_e.a);
        desb.push_back(in_e.b);
        vec.push_back(in_e);
    }
    
    for (int i = 0; i < Q; i++){
        in_e.id = i + 1;
        cin >> in_e.a >> in_e.b >> in_e.sum;
        desa.push_back(-in_e.a);
        desb.push_back(in_e.b);
        vec.push_back(in_e);
    }

    sort(desa.begin(), desa.end());
    sort(desb.begin(), desb.end());
    sort(vec.begin(), vec.end(), cmp);

    for(auto i:vec){
        if(i.id){
            ans[i.id] = query_BIT(getposa(i.a), getposb(i.b));
        }
        else{
            modify_BIT(getposa(i.a), getposb(i.b));
        }
    }

    for (int i = 1; i <= Q; i++){
        cout << ans[i] << '\n';
    }

    uwu
}

Compilation message (stderr)

examination.cpp: In function 'void modify_BIT(int, int)':
examination.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (; posa <= desa.size(); posa += (posa &  - posa)){
      |            ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57