oj.uz

Submission #858616

# Submission time Handle Problem Language Result Execution time Memory
858616 2023-10-09T02:16:56 Z sleepntsheep Examination (JOI19_examination) C++17
100 / 100
 2496 ms 229232 KB 
#include <cstdio> 
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define int long long
using iset = tree<pair<int, int>, null_type, greater<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;

#define N 200005
#define ALL(x) x.begin(), x.end()

int n, q, C, ans[N];
iset t[N*5];

void Ins(int v, int l, int r, int p, int k)
{
    t[v].insert(make_pair(k, ++C));
    if (l != r)
    {
        if (p <= (l+r)/2)
            Ins(2*v+1, l, (l+r)/2, p, k);
        else
            Ins(2*v+2, (l+r)/2+1, r, p, k);
    }
}

int Qry(int v, int l, int r, int x, int y, int k)
{
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) 
    {
        return t[v].order_of_key(*t[v].lower_bound(make_pair(k, 0))); 
    }
    return Qry(2*v+1, l, (l+r)/2, x, y, k) + Qry(2*v+2, (l+r)/2+1, r, x, y, k);
}

struct qry
{
    int x, y, z, i, cx;
    bool operator<(const qry &a) const { return z > a.z; }
} b[N];

struct ppl
{
    int x, y, cx;
    bool operator<(const ppl &a) const { return x+y > a.x + a.y; }
} a[N];

int crd = 0;
void compress()
{
    vector<int> v;
    for (int i = 0; i < n; ++i) v.push_back(a[i].x);
    for (int i = 0; i < q; ++i) v.push_back(b[i].x);
    sort(ALL(v));
    v.erase(unique(ALL(v)), v.end());
    for (int i = 0; i < n; ++i) a[i].cx = lower_bound(ALL(v), a[i].x) - v.begin() + 1;
    for (int i = 0; i < q; ++i) b[i].cx = lower_bound(ALL(v), b[i].x) - v.begin() + 1;
    crd = v.size();
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;
    for (int i = 0; i < q; ++i) cin >> b[i].x >> b[i].y >> b[i].z, b[i].i = i;

    compress();
    sort(a, a+n);
    sort(b, b+q);

    int j = 0;
    for (int i = 0; i < q; ++i)
    {
        for (; j < n && a[j].x + a[j].y >= b[i].z; ++j)
            Ins(0, 1, 2*n, a[j].cx, a[j].y);
        ans[b[i].i] = Qry(0, 1, 2*n, b[i].cx, crd, b[i].y);
    }

    for (int i = 0; i < q; ++i) 
    {
        cout << ans[i] << '\n';
    }

    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 97872 KB Output is correct
2 Correct 53 ms 97876 KB Output is correct
3 Correct 54 ms 97872 KB Output is correct
4 Correct 52 ms 97872 KB Output is correct
5 Correct 53 ms 97872 KB Output is correct
6 Correct 52 ms 97960 KB Output is correct
7 Correct 67 ms 100664 KB Output is correct
8 Correct 64 ms 100692 KB Output is correct
9 Correct 66 ms 100688 KB Output is correct
10 Correct 72 ms 100576 KB Output is correct
11 Correct 71 ms 100724 KB Output is correct
12 Correct 68 ms 100672 KB Output is correct
13 Correct 67 ms 100724 KB Output is correct
14 Correct 68 ms 100556 KB Output is correct
15 Correct 68 ms 101012 KB Output is correct
16 Correct 64 ms 100652 KB Output is correct
17 Correct 70 ms 100580 KB Output is correct
18 Correct 65 ms 100436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1992 ms 223748 KB Output is correct
2 Correct 2025 ms 226236 KB Output is correct
3 Correct 1982 ms 226432 KB Output is correct
4 Correct 1291 ms 225724 KB Output is correct
5 Correct 902 ms 226584 KB Output is correct
6 Correct 871 ms 225896 KB Output is correct
7 Correct 1781 ms 226372 KB Output is correct
8 Correct 1769 ms 226364 KB Output is correct
9 Correct 1627 ms 226408 KB Output is correct
10 Correct 749 ms 227620 KB Output is correct
11 Correct 1002 ms 225492 KB Output is correct
12 Correct 1298 ms 226908 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1992 ms 223748 KB Output is correct
2 Correct 2025 ms 226236 KB Output is correct
3 Correct 1982 ms 226432 KB Output is correct
4 Correct 1291 ms 225724 KB Output is correct
5 Correct 902 ms 226584 KB Output is correct
6 Correct 871 ms 225896 KB Output is correct
7 Correct 1781 ms 226372 KB Output is correct
8 Correct 1769 ms 226364 KB Output is correct
9 Correct 1627 ms 226408 KB Output is correct
10 Correct 749 ms 227620 KB Output is correct
11 Correct 1002 ms 225492 KB Output is correct
12 Correct 1298 ms 226908 KB Output is correct
13 Correct 1860 ms 226648 KB Output is correct
14 Correct 2132 ms 226772 KB Output is correct
15 Correct 1979 ms 226388 KB Output is correct
16 Correct 1176 ms 225832 KB Output is correct
17 Correct 912 ms 226948 KB Output is correct
18 Correct 869 ms 225728 KB Output is correct
19 Correct 1827 ms 226888 KB Output is correct
20 Correct 2063 ms 226844 KB Output is correct
21 Correct 1616 ms 227084 KB Output is correct
22 Correct 748 ms 227216 KB Output is correct
23 Correct 1016 ms 225564 KB Output is correct
24 Correct 1298 ms 226748 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 97872 KB Output is correct
2 Correct 53 ms 97876 KB Output is correct
3 Correct 54 ms 97872 KB Output is correct
4 Correct 52 ms 97872 KB Output is correct
5 Correct 53 ms 97872 KB Output is correct
6 Correct 52 ms 97960 KB Output is correct
7 Correct 67 ms 100664 KB Output is correct
8 Correct 64 ms 100692 KB Output is correct
9 Correct 66 ms 100688 KB Output is correct
10 Correct 72 ms 100576 KB Output is correct
11 Correct 71 ms 100724 KB Output is correct
12 Correct 68 ms 100672 KB Output is correct
13 Correct 67 ms 100724 KB Output is correct
14 Correct 68 ms 100556 KB Output is correct
15 Correct 68 ms 101012 KB Output is correct
16 Correct 64 ms 100652 KB Output is correct
17 Correct 70 ms 100580 KB Output is correct
18 Correct 65 ms 100436 KB Output is correct
19 Correct 1992 ms 223748 KB Output is correct
20 Correct 2025 ms 226236 KB Output is correct
21 Correct 1982 ms 226432 KB Output is correct
22 Correct 1291 ms 225724 KB Output is correct
23 Correct 902 ms 226584 KB Output is correct
24 Correct 871 ms 225896 KB Output is correct
25 Correct 1781 ms 226372 KB Output is correct
26 Correct 1769 ms 226364 KB Output is correct
27 Correct 1627 ms 226408 KB Output is correct
28 Correct 749 ms 227620 KB Output is correct
29 Correct 1002 ms 225492 KB Output is correct
30 Correct 1298 ms 226908 KB Output is correct
31 Correct 1860 ms 226648 KB Output is correct
32 Correct 2132 ms 226772 KB Output is correct
33 Correct 1979 ms 226388 KB Output is correct
34 Correct 1176 ms 225832 KB Output is correct
35 Correct 912 ms 226948 KB Output is correct
36 Correct 869 ms 225728 KB Output is correct
37 Correct 1827 ms 226888 KB Output is correct
38 Correct 2063 ms 226844 KB Output is correct
39 Correct 1616 ms 227084 KB Output is correct
40 Correct 748 ms 227216 KB Output is correct
41 Correct 1016 ms 225564 KB Output is correct
42 Correct 1298 ms 226748 KB Output is correct
43 Correct 1967 ms 229188 KB Output is correct
44 Correct 1937 ms 228668 KB Output is correct
45 Correct 2496 ms 228828 KB Output is correct
46 Correct 1319 ms 227072 KB Output is correct
47 Correct 956 ms 228020 KB Output is correct
48 Correct 828 ms 225404 KB Output is correct
49 Correct 2017 ms 228512 KB Output is correct
50 Correct 1701 ms 228796 KB Output is correct
51 Correct 1672 ms 228588 KB Output is correct
52 Correct 1348 ms 229232 KB Output is correct
53 Correct 1020 ms 226196 KB Output is correct