제출 #1351483

#제출 시각아이디문제언어결과실행 시간메모리
1351483kantaponzExamination (JOI19_examination)C++20
100 / 100
221 ms55360 KiB
#include <bits/stdc++.h>
using namespace std;

const int nx = 1e5 + 5;
const int cx = 3e5 + 5;

int n, q;
int s[nx], t[nx], a[nx], b[nx], c[nx];
vector<int> qrs1[cx], qrs2[cx], qrs3[cx], vec1[cx], vec2[cx], vec3[cx];
vector<int> sum;
int tree[cx];
int ex1[nx], ex2[nx];
int ans[nx];

void reset_tree() {memset(tree, 0, sizeof tree);}

void update(int idx, int val) {
    for (int i = idx; i >= 1; i -= (i & -i)) tree[i] += val;
}

int query(int idx) {
    int ans = 0;
    for (int i = idx; i < cx; i += (i & -i)) ans += tree[i];
    return ans;
}


int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    vector<int> v;
    sum.emplace_back(0);
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> t[i];
        v.push_back(s[i]);
        v.push_back(s[i] + t[i]);
        v.push_back(t[i]);
        sum.emplace_back(s[i] + t[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()), v.end());
    sort(sum.begin(), sum.end());

    for (int i = 1; i <= n; i++) sum[i] = lower_bound(v.begin(), v.end(), sum[i]) - v.begin() + 1;

    /*for (auto x : v) cout << x << " ";
    cout << endl;*/

    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i];
        if (a[i] + b[i] >= c[i]) {
            int idx = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            qrs1[idx].emplace_back(i);
        } else {
            int idx1 = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            int idx2 = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1;
            qrs2[idx1].emplace_back(i);
            qrs3[idx2].emplace_back(i);
        }
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1;
        c[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin() + 1;
        //cout << a[i] << " " << b[i] << " " << c[i] << endl;
    }

    for (int i = 1; i <= n; i++) {
        int idx1 = lower_bound(v.begin(), v.end(), s[i]) - v.begin() + 1;
        int idx2 = lower_bound(v.begin(), v.end(), t[i]) - v.begin() + 1;
        int idx3 = lower_bound(v.begin(), v.end(), s[i] + t[i]) - v.begin() + 1;
        vec2[idx1].emplace_back(idx3);
        vec3[idx2].emplace_back(idx3);
        vec1[idx1].emplace_back(idx2);
        s[i] = idx1;
        t[i] = idx2;
    }

    // calculate qrs1

    memset(ans, -1, sizeof ans);

    for (int i = cx - 1; i >= 1; i--) {
        for (auto idx : vec1[i]) update(idx, 1);
        for (auto idx : qrs1[i]) {
            ans[idx] = query(b[idx]);
        }
    }   

    reset_tree();

    for (int i = 1; i < cx; i++) {
        for (auto idx : qrs2[i]) {
            ex1[idx] = query(c[idx]);
        }
        for (auto idx : vec2[i]) update(idx, 1);
    }

    reset_tree();

    for (int i = 1; i < cx; i++) {
        for (int idx : qrs3[i]) {
            ex2[idx] = query(c[idx]);
        }
        for (int idx : vec3[i]) update(idx, 1);
    }

    for (int i = 1; i <= q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << "\n";
            continue;
        }
        int ct = lower_bound(sum.begin(),sum.end(),c[i]) - sum.begin();
        ans[i] = n - ct + 1 - ex1[i] - ex2[i];
        cout << ans[i] << "\n";
    }



}

/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100



10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117


*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...