Submission #1314105

#TimeUsernameProblemLanguageResultExecution timeMemory
1314105ladnooooExamination (JOI19_examination)C++20
100 / 100
413 ms15248 KiB
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define int long long
#define pb push_back

using ordered_set = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

const int maxN = 1e5 + 7;

int a[maxN], b[maxN];
int ans[maxN];

vector<array<int, 4>> v;

bool cmp(array<int, 4> a, array<int, 4> b) {
    if (a[0] != b[0]) return a[0] < b[0];
    return a[3] > b[3];
}

bool cmp2(array<int, 4> a, array<int, 4> b) {
    return a[1] > b[1];
}

void dnc(int l, int r) {
    if(l >= r) return;
    int m = (l + r) / 2;
    dnc(l, m);
    dnc(m + 1, r);

    ordered_set st;

    sort(v.begin() + l, v.begin() + m + 1, cmp2);
    sort(v.begin() + m + 1, v.begin() + r + 1, cmp2);

    int ff = m;
    for (int i = l; i <= m; i++) {
        while (ff + 1 <= r && v[ff + 1][1] >= v[i][1]) {
            ++ff;
            if (v[ff][3] == 0) st.insert({v[ff][2], ff});
        }
        if (v[i][3] > 0) ans[v[i][3]] += st.size() - st.order_of_key({v[i][2], 0});
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        int s = a[i] + b[i];
        v.pb({a[i], b[i], s, 0});
    }
    for(int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v.pb({x, y, z, i});
    }
    sort(v.begin(), v.end(), cmp);
    dnc(0, n + m - 1);
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

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