oj.uz

Submission #471328

# Submission time Handle Problem Language Result Execution time Memory
471328 2021-09-08T12:33:28 Z spike1236 Examination (JOI19_examination) C++14
0 / 100
 3000 ms 191856 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]] = 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 288 ms 33616 KB Output is correct
8 Correct 315 ms 33916 KB Output is correct
9 Correct 288 ms 34264 KB Output is correct
10 Execution timed out 3035 ms 972 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 191856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 191856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 288 ms 33616 KB Output is correct
8 Correct 315 ms 33916 KB Output is correct
9 Correct 288 ms 34264 KB Output is correct
10 Execution timed out 3035 ms 972 KB Time limit exceeded
11 Halted 0 ms 0 KB -