oj.uz

Submission #702416

# Submission time Handle Problem Language Result Execution time Memory
702416 2023-02-24T03:06:48 Z PixelCat Examination (JOI19_examination) C++14
20 / 100
 3000 ms 65548 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;

#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
struct SegTree {
    vector<int> st[MAXN << 2], t[MAXN << 2];
    void build(int id, int l, int r, vector<int> &vs, vector<vector<int>> &vt) {
        For(it, l, r) for(auto &j:vt[it]) {
            t[id].eb(j);
            st[id].eb(vs[it] + j);
        }
        sort(all(t[id]));
        sort(all(st[id]));
        if(l == r) return;
        int m = (l + r) / 2;
        build(L(id), l, m, vs, vt);
        build(R(id), m + 1, r, vs, vt);
    }
    int count(const vector<int> &v, int x) {
        return v.end() - lower_bound(all(v), x);
    }
    int ask(int id, int l, int r, int L, int R, int type, int x) {
        if(l >= L && r <= R) {
            if(type) return count(t[id], x);
            return count(st[id], x);
        }
        int m = (l + r) / 2;
        if(R <= m) return ask(L(id), l, m, L, R, type, x);
        if(L > m)  return ask(R(id), m + 1, r, L, R, type, x);
        return ask(L(id), l, m, L, R, type, x) +
               ask(R(id), m + 1, r, L, R, type, x);
    }
} seg;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nyanyanyanyanya
    int n, q; cin >> n >> q;
    vector<pii> pts;
    vector<int> vs;
    For(i, 1, n) {
        int s, t; cin >> s >> t;
        pts.eb(s, t);
        vs.eb(s);
    }
    sort(all(vs));
    vs.erase(unique(all(vs)), vs.end());
    int m = sz(vs);
    vector<vector<int>> vt(m);
    for(auto &p:pts) {
        int it = lower_bound(all(vs), p.F) - vs.begin();
        vt[it].eb(p.S);
    }
    seg.build(0, 0, m - 1, vs, vt);
    while(q--) {
        int a, b, c; cin >> a >> b >> c;
        int res;
        if(a + b >= c) {
            int p = lower_bound(all(vs), a) - vs.begin();
            res = seg.ask(0, 0, m - 1, p, m, 1, b);
        } else {
            int p1 = lower_bound(all(vs), a) - vs.begin();
            int p2 = lower_bound(all(vs), c - b) - vs.begin();
            res = seg.ask(0, 0, m - 1, p1, p2 - 1, 0, c) +
                  seg.ask(0, 0, m - 1, p2, m, 1, b);
        }
        cout << res << "\n";
    }
    return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 65404 KB Output is correct
2 Correct 386 ms 65356 KB Output is correct
3 Correct 393 ms 65548 KB Output is correct
4 Correct 319 ms 64668 KB Output is correct
5 Correct 138 ms 33236 KB Output is correct
6 Correct 85 ms 32568 KB Output is correct
7 Correct 369 ms 65292 KB Output is correct
8 Correct 366 ms 65484 KB Output is correct
9 Correct 343 ms 65316 KB Output is correct
10 Correct 70 ms 27964 KB Output is correct
11 Correct 241 ms 64448 KB Output is correct
12 Correct 47 ms 27068 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 65404 KB Output is correct
2 Correct 386 ms 65356 KB Output is correct
3 Correct 393 ms 65548 KB Output is correct
4 Correct 319 ms 64668 KB Output is correct
5 Correct 138 ms 33236 KB Output is correct
6 Correct 85 ms 32568 KB Output is correct
7 Correct 369 ms 65292 KB Output is correct
8 Correct 366 ms 65484 KB Output is correct
9 Correct 343 ms 65316 KB Output is correct
10 Correct 70 ms 27964 KB Output is correct
11 Correct 241 ms 64448 KB Output is correct
12 Correct 47 ms 27068 KB Output is correct
13 Execution timed out 3063 ms 64444 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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