Submission #328605

#	Time	Username	Problem	Language	Result	Execution time	Memory
328605		jovan_b	Examination (JOI19_examination)	C++17	100 / 100	851 ms	47708 KiB

examination

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct BIT{
    int n;
    int val[1000000];
    int get(int x){
        int res = 0;
        while(x){
            res += val[x];
            x -= x & -x;
        }
        return res;
    }
    void add(int x, int vrd){
        while(x <= n){
            val[x] += vrd;
            x += x & -x;
        }
    }
};

struct query{
    int x, y, z, ind;
};

bool cmp1(query a, query b){
    if(a.x == b.x) return a.ind > b.ind;
    return a.x < b.x;
}

bool cmp2(query a, query b){
    if(a.z == b.z) return a.ind > b.ind;
    return a.z < b.z;
}

pair <int, int> niz[100005];
map <int, int> compr;
int tcomp;
query queries1[200005], queries2[200005];
int res[100005];

int main(){
    ios_base::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector <int> compvec;
    for(int i=1; i<=n; i++){
        cin >> niz[i].first >> niz[i].second;
        compvec.push_back(niz[i].first);
        compvec.push_back(niz[i].second);
        compvec.push_back(niz[i].first+niz[i].second);
    }
    int q1 = 0, q2 = 0;
    for(int i=1; i<=q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        compvec.push_back(x);
        compvec.push_back(y);
        compvec.push_back(z);
        query tq;
        tq.x = x, tq.y = y, tq.z = z, tq.ind = i;
        if(z <= x+y) queries1[++q1] = tq;
        else queries2[++q2] = tq;
    }
    for(int i=1; i<=n; i++){
        query tq;
        tq.x = niz[i].first;
        tq.y = niz[i].second;
        tq.ind = tq.z = 0;
        queries1[++q1] = tq;
    }
    sort(compvec.begin(), compvec.end());
    for(auto c : compvec){
        if(!compr[c]) compr[c] = ++tcomp;
    }
    sort(queries1+1, queries1+1+q1, cmp1);
    int bilo = 0;
    BIT sam;
    sam.n = 1000000;
    for(int i=q1; i>=1; i--){
        if(queries1[i].ind == 0){
            bilo++;
            sam.add(compr[queries1[i].y], 1);
        }
        else{
            res[queries1[i].ind] += bilo - sam.get(compr[queries1[i].y]-1);
        }
    }

    for(int i=1; i<=n; i++){
        query tq;
        tq.x = niz[i].first;
        tq.y = niz[i].second;
        tq.z = niz[i].first + niz[i].second;
        tq.ind = 0;
        queries2[++q2] = tq;
    }
    sort(queries2+1, queries2+1+q2, cmp2);
    BIT prvo, drugo;
    bilo = 0;
    prvo.n = drugo.n = 1000000;
    for(int i=q2; i>=1; i--){
        if(queries2[i].ind == 0){
            bilo++;
            prvo.add(compr[queries2[i].x], 1);
            drugo.add(compr[queries2[i].y], 1);
        }
        else{
            res[queries2[i].ind] += bilo - prvo.get(compr[queries2[i].x]-1) - drugo.get(compr[queries2[i].y]-1);
        }
    }
    for(int i=1; i<=q; i++) cout << res[i] << "\n";
    return 0;
}

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