제출 #471328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471328		spike1236	Examination (JOI19_examination)	C++14	0 / 100	3087 ms	191856 KiB

examination

#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define f first
#define s second

const int MAXN = 1e5 + 10;
pair <int, int> a[MAXN];
map <int, vector <vector <int> > > q;
unordered_map <int, unordered_map <int, int> > fw;
int ans[MAXN];

void upd(int x, int y, int val) {
    for(long long j = x; j <= 2e9; j += j & -j) {
        for(long long z = y; z <= 2e9; z += z & -z) {
            fw[j][z] += val;
        }
    }
}

int get(int x, int y) {
    int res = 0;
    for(int i = x; i > 0; i -= i & -i) {
        if(!fw.count(i)) continue;
        for(int j = y; j > 0; j -= j & -j) {
            if(!fw[i].count(j)) continue;
            res += fw[i][j];
        }
    }
    return res;
}

int get(int x1, int y1, int x2, int y2) {
    return get(x2, y2) - get(x1 - 1, y2) - get(x2 - 1, y1) + get(x1, y1);
}

int main() {
    int n, qq;
    cin >> n >> qq;
    for(int i = 0; i < n; ++i) cin >> a[i].f >> a[i].s;
    sort(a, a + n);
    int x, y, z;
    for(int i = 0; i < qq; ++i) {
        cin >> x >> y >> z;
        q[x].push_back({y, z, i});
    }
    for(int i = 0; i < n; ++i) upd(a[i].s, a[i].f + a[i].s, 1);
    int ptr = 0;
    for(auto it : q) {
        while(ptr < n && a[ptr].f < it.f) {
            upd(a[ptr].s, a[ptr].f + a[ptr].s, -1);
            ++ptr;
        }
        for(auto j : q[it.f]) {
            ans[j[2]] = n - ptr - get(j[0] - 1, 2e9) - get(2e9, j[1] - 1) + get(j[0] - 1, j[1] - 1);
        }
    }
    for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
    return 0;
}

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