Submission #1126671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126671		KK_1729	Examination (JOI19_examination)	C++17	100 / 100	967 ms	89440 KiB

examination

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

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back 
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

struct Fenwick{
    int N;
    vector<int> tree;


    Fenwick (int n){
        this->N = n;
        tree.resize(N+1);
    }
    
    int sum(int k) {
        if (k == 0) return 0;
        int s = 0;
        while (k >= 1) {
            s += tree[k];
            k -= k&-k;
        }
        return s;
    }

    void add(int k, int x) {
        while (k <= N) {
            tree[k] += x;
            k += k&-k;
        }
    }

    int query(int l, int r){
        int ans = sum(r);
        if (l > 1) ans -= sum(l-1);
        return ans;
    }
};
void solve(){
    int n, q; cin >> n >> q;

    vector<vector<int>> scores;
    set<int> se;
    FOR(i,0,n){
        int s, t; cin >> s >> t;
        scores.pb({s+t, s, t});
        se.insert(s);
        se.insert(t);
        se.insert(s+t);
    }

    vector<vector<int>> teachers;
    FOR(i,0,q){
        int x, y, z; cin >> x >> y >> z;
        z = max(z, x+y);
        teachers.pb({z, x, y, i});
        se.insert(x);
        se.insert(y);
        se.insert(z);
    }

    int ptr = 1;
    map<int, int> cc;
    for (auto x: se){
        cc[x] = ptr;ptr++;
    }

    FOR(i,0,n) scores[i] = {cc[scores[i][0]], cc[scores[i][1]], cc[scores[i][2]]};
    FOR(i,0,q) teachers[i] = {cc[teachers[i][0]], cc[teachers[i][1]], cc[teachers[i][2]], teachers[i][3]};

    sort(all(scores));reverse(all(scores));
    sort(all(teachers));reverse(all(teachers));

    Fenwick math(ptr+1);
    Fenwick informatics(ptr+1);

    int curr = 0;
    vector<int> answer(q);
    FOR(i,0,q){
        while (curr < n && scores[curr][0] >= teachers[i][0]){
            math.add(scores[curr][1], 1);
            informatics.add(scores[curr][2], 1);
            curr++;
        }

        int ans = math.sum(teachers[i][1]-1) + informatics.sum(teachers[i][2]-1);
        answer[teachers[i][3]] = curr-ans;
    }


    FOR(i,0,q) cout << answer[i] << endl;
    // cout << endl;
}

int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}

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