oj.uz

답안 #471324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471324 2021-09-08T12:00:55 Z spike1236 Examination (JOI19_examination) C++14
0 / 100
 3000 ms 179528 KB 
#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]] = get(j[0], j[1], 2e9, 2e9);
    }
    for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 1 ms 288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3077 ms 179528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3077 ms 179528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 1 ms 288 KB Output isn't correct
4 Halted 0 ms 0 KB -