제출 #1328837

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

#define int long long
#define N 500005
#define f first
#define s second

const int inf = 1e18;

int tc = 1, n, c[N], b[N], Q, ans[N], sm[N];
vector <tuple <int,int,int,int>> q;
vector <int> fn[N];
pair <int,int> a[N];
map <int,int> vis;

void upd(int x,int y) {
    for(; x > 0; x -= (x & (-x))) {
        fn[x].push_back(y);
        sort(fn[x].begin(),fn[x].end());
    }
}
int solve(int x,int y) {
    int s = 0;
    for(; x < N; x += (x & (-x))) {
        int l = lower_bound(fn[x].begin(),fn[x].end(), y) - fn[x].begin();
        s += ((int)fn[x].size() - l);
    }
    return s;
}


int32_t main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].f >> a[i].s;
        int sum = a[i].f + a[i].s;
        vis[a[i].s] = vis[a[i].f] = vis[sum] = 1;
    }
    for(int i = 1; i <= Q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        vis[x] = vis[y] = vis[z] = 1;
        q.push_back({x, y, z, i});
    }
    int inx = 1;
    for(auto i : vis) {
        vis[i.first] = inx++;
    }
    sort(q.rbegin(),q.rend());
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        sm[i] = vis[a[i].f + a[i].s];
        a[i].f = vis[a[i].f];
        a[i].s = vis[a[i].s];
    }
    int ind = n;
    for(int i = 0; i < Q; i++) {
        int x, y, z, pos;
        tie(x, y, z, pos) = q[i];
        x = vis[x];
        y = vis[y];
        z = vis[z];
        while(ind >= 1 && a[ind].f >= x) {
            upd(a[ind].s, sm[ind]);
            ind--;
        }
        ans[pos] = solve(y, z);
    }
    cout << endl;
    for(int i = 1; i <= Q; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...