oj.uz

Submission #471329

# Submission time Handle Problem Language Result Execution time Memory
471329 2021-09-08T12:37:35 Z spike1236 Examination (JOI19_examination) C++14
0 / 100
 3000 ms 35568 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 <= 1e9; j += j & -j) {
        for(long long z = y; z <= 1e9; 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;
}

bool cmp(const pair <int, int> &x, const pair <int, int> &y) {
    return (x.f + x.s < y.f + y.s);
}

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, &cmp);
    int x, y, z;
    for(int i = 0; i < qq; ++i) {
        cin >> x >> y >> z;
        q[z].push_back({x, y, i});
    }
    for(int i = 0; i < n; ++i) upd(a[i].f, a[i].s, 1);
    int ptr = 0;
    for(auto it : q) {
        while(ptr < n && a[ptr].f + a[ptr].s < it.f) {
            upd(a[ptr].f, a[ptr].s, -1);
            ++ptr;
        }
        for(auto j : q[it.f]) {
            ans[j[2]] = n - ptr - get(j[0] - 1, 1e9) - get(1e9, 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 Execution timed out 3058 ms 332 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 35568 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 3075 ms 35568 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 Execution timed out 3058 ms 332 KB Time limit exceeded
3 Halted 0 ms 0 KB -