Submission #1317186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317186		buzdi	Examination (JOI19_examination)	C++17	100 / 100	609 ms	18208 KiB

examination

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int NMAX = 1e5;

struct Triplet {
    int x, y, z, ind;
}v[2 * NMAX + 1], c[2 * NMAX + 1];

struct AIB {
    int n;
    int aib[2 * NMAX + 1];
    void init(int n) {
        this->n = n;
        fill(aib + 1, aib + n + 1, 0);
    }

    void update(int pos, int value) {
        for(int i = pos; i <= n; i += i & (-i)) {
            aib[i] += value;
        }
    }

    int query(int pos) {
        int answer = 0;
        for(int i = pos; i >= 1; i -= i & (-i)) {
            answer += aib[i];
        }
        return answer;
    }
}aib;

int n, q, ID, ind;
int updates[2 * NMAX + 1];
int answer[NMAX + 1];
map<int, int> mp;

bool cmp(const Triplet& a, const Triplet& b) {
    if(a.x != b.x) {
        return a.x > b.x;
    }
    return a.ind < b.ind;
}

void cdq(int left, int right) {
    if(left == right) {
        return;
    }
    int mid = (left + right) / 2;
    cdq(left, mid);
    cdq(mid + 1, right);

    int i = left, j = mid + 1, ind = 0, ind_upd = 0;
    while(i <= mid && j <= right) {
        if(v[i].y >= v[j].y) {
            if(!v[i].ind) {
                aib.update(mp[v[i].z], 1);
                updates[++ind_upd] = mp[v[i].z];
            }
            c[++ind] = v[i];
            i++;
        }
        else {
            if(v[j].ind) {
                answer[v[j].ind] += aib.query(ID) - aib.query(mp[v[j].z] - 1);
            }
            c[++ind] = v[j];
            j++;
        }
    }
    while(i <= mid) {
        c[++ind] = v[i];
        i++;
    }
    while(j <= right) {
        if(v[j].ind) {
            answer[v[j].ind] += aib.query(ID) - aib.query(mp[v[j].z] - 1);
        }
        c[++ind] = v[j];
        j++;
    }

    for(int i = 1; i <= ind_upd; i++) {
        aib.update(updates[i], -1);
    }
    for(int i = left; i <= right; i++) {
        v[i] = c[i - left + 1];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int s, t;
        cin >> s >> t;
        v[++ind] = {s, t, s + t, 0LL};
    }

    for(int i = 1; i <= q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v[++ind] = {x, y, z, i};
    }

    for(int i = 1; i <= ind; i++) {
        mp[v[i].z] = 1;
    }
    for(auto& x : mp) {
        x.second = ++ID;
    }

    sort(v + 1, v + ind + 1, cmp);
    aib.init(ID);
    cdq(1, ind);
    for(int i = 1; i <= q; i++) {
        cout << answer[i] << '\n';
    }
    return 0;
}

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