oj.uz

Submission #786749

# Submission time Handle Problem Language Result Execution time Memory
786749 2023-07-18T12:26:55 Z PanosPask Examination (JOI19_examination) C++14
100 / 100
 620 ms 19412 KB 
#include <bits/stdc++.h>

using namespace std;

const int QUERY = 1;
const int STUDENT = 0;

struct BITree {
    int size;
    vector<int> tree;

    void init(int n) {
        size = n;
        tree.assign(size, 0);
    }

    void add(int i, int v) {
        for (int x = i; x < size; x = x | (x + 1))
            tree[x] += v;
    }

    int get(int i) {
        int res = 0;
        for (int x = i; x >= 0; x = (x & (x + 1)) - 1)
            res += tree[x];
        return res;
    }
    int get(int l, int r) {
        int a = get(r - 1);
        int b = get(l - 1);

        return a - b;
    }
    int rget(int i) {
        return get(i, size);
    }
};

struct Event {
    int type;
    int x, y;
    int z;
    int id;
};
bool sumsort(const Event& a, const Event& b)
{
    if (a.z == b.z)
        return a.type < b.type;
    return a.z > b.z;
}
bool xsort(const Event& a, const Event& b)
{
    return a.x > b.x;
}

BITree b;
int N, Q;
vector<int> ycords;
vector<int> ans;
vector<Event> initial;

int find(int v)
{
    return lower_bound(ycords.begin(), ycords.end(), v) - ycords.begin();
}

void add_student(const Event& s, int mul = 1)
{
    if (s.type == QUERY)
        return;

    b.add(find(s.y), 1 * mul);
}
void make_query(const Event& s)
{
    if (s.type == STUDENT)
        return;

    ans[s.id] += b.rget(find(s.y));
}

void cdq_dc(vector<Event>& events)
{
    if (events.size() == 1) {
        // Nothing can be done
        return;
    }

    int mid = events.size() / 2;
    vector<Event> e1(mid), e2(events.size() - mid);

    for (int i = 0; i < mid; i++)
        e1[i] = events[i];
    for (int i = mid; i < events.size(); i++)
        e2[i - mid] = events[i];

    cdq_dc(e1);
    cdq_dc(e2);

    sort(e1.begin(), e1.end(), xsort);
    sort(e2.begin(), e2.end(), xsort);

    int to_add = 0;
    for (auto e : e2) {
        while (to_add < e1.size() && e1[to_add].x >= e.x) {
            add_student(e1[to_add]);
            to_add++;
        }

        make_query(e);
    }

    while (to_add) {
        to_add--;
        add_student(e1[to_add], -1);
    }
}

int main(void)
{
    scanf("%d %d", &N, &Q);

    ans.resize(Q);

    for (int i = 0; i < N; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        ycords.push_back(y);

        initial.push_back({STUDENT, x, y, x + y, -1});
    }
    for (int i = 0; i < Q; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        ycords.push_back(y);

        initial.push_back({QUERY, x, y, z, i});
    }
    sort(initial.begin(), initial.end(), sumsort);
    sort(ycords.begin(), ycords.end());
    ycords.resize(unique(ycords.begin(), ycords.end()) - ycords.begin());

    b.init(ycords.size());
    cdq_dc(initial);

    for (int i = 0; i < Q; i++)
        printf("%d\n", ans[i]);

    return 0;
}

Compilation message

examination.cpp: In function 'void cdq_dc(std::vector<Event>&)':
examination.cpp:94:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = mid; i < events.size(); i++)
      |                       ~~^~~~~~~~~~~~~~~
examination.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         while (to_add < e1.size() && e1[to_add].x >= e.x) {
      |                ~~~~~~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 11 ms 824 KB Output is correct
8 Correct 11 ms 852 KB Output is correct
9 Correct 11 ms 828 KB Output is correct
10 Correct 7 ms 692 KB Output is correct
11 Correct 10 ms 724 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 10 ms 852 KB Output is correct
14 Correct 10 ms 864 KB Output is correct
15 Correct 11 ms 860 KB Output is correct
16 Correct 9 ms 724 KB Output is correct
17 Correct 7 ms 724 KB Output is correct
18 Correct 4 ms 736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 16572 KB Output is correct
2 Correct 551 ms 16604 KB Output is correct
3 Correct 559 ms 16612 KB Output is correct
4 Correct 280 ms 15476 KB Output is correct
5 Correct 423 ms 15840 KB Output is correct
6 Correct 214 ms 14756 KB Output is correct
7 Correct 538 ms 16480 KB Output is correct
8 Correct 512 ms 16412 KB Output is correct
9 Correct 511 ms 16308 KB Output is correct
10 Correct 353 ms 15588 KB Output is correct
11 Correct 228 ms 15400 KB Output is correct
12 Correct 156 ms 14340 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 16572 KB Output is correct
2 Correct 551 ms 16604 KB Output is correct
3 Correct 559 ms 16612 KB Output is correct
4 Correct 280 ms 15476 KB Output is correct
5 Correct 423 ms 15840 KB Output is correct
6 Correct 214 ms 14756 KB Output is correct
7 Correct 538 ms 16480 KB Output is correct
8 Correct 512 ms 16412 KB Output is correct
9 Correct 511 ms 16308 KB Output is correct
10 Correct 353 ms 15588 KB Output is correct
11 Correct 228 ms 15400 KB Output is correct
12 Correct 156 ms 14340 KB Output is correct
13 Correct 576 ms 17012 KB Output is correct
14 Correct 560 ms 16956 KB Output is correct
15 Correct 555 ms 16616 KB Output is correct
16 Correct 327 ms 15928 KB Output is correct
17 Correct 449 ms 16216 KB Output is correct
18 Correct 245 ms 14724 KB Output is correct
19 Correct 554 ms 17028 KB Output is correct
20 Correct 568 ms 16988 KB Output is correct
21 Correct 537 ms 16980 KB Output is correct
22 Correct 351 ms 15676 KB Output is correct
23 Correct 218 ms 15264 KB Output is correct
24 Correct 158 ms 14340 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 11 ms 824 KB Output is correct
8 Correct 11 ms 852 KB Output is correct
9 Correct 11 ms 828 KB Output is correct
10 Correct 7 ms 692 KB Output is correct
11 Correct 10 ms 724 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 10 ms 852 KB Output is correct
14 Correct 10 ms 864 KB Output is correct
15 Correct 11 ms 860 KB Output is correct
16 Correct 9 ms 724 KB Output is correct
17 Correct 7 ms 724 KB Output is correct
18 Correct 4 ms 736 KB Output is correct
19 Correct 544 ms 16572 KB Output is correct
20 Correct 551 ms 16604 KB Output is correct
21 Correct 559 ms 16612 KB Output is correct
22 Correct 280 ms 15476 KB Output is correct
23 Correct 423 ms 15840 KB Output is correct
24 Correct 214 ms 14756 KB Output is correct
25 Correct 538 ms 16480 KB Output is correct
26 Correct 512 ms 16412 KB Output is correct
27 Correct 511 ms 16308 KB Output is correct
28 Correct 353 ms 15588 KB Output is correct
29 Correct 228 ms 15400 KB Output is correct
30 Correct 156 ms 14340 KB Output is correct
31 Correct 576 ms 17012 KB Output is correct
32 Correct 560 ms 16956 KB Output is correct
33 Correct 555 ms 16616 KB Output is correct
34 Correct 327 ms 15928 KB Output is correct
35 Correct 449 ms 16216 KB Output is correct
36 Correct 245 ms 14724 KB Output is correct
37 Correct 554 ms 17028 KB Output is correct
38 Correct 568 ms 16988 KB Output is correct
39 Correct 537 ms 16980 KB Output is correct
40 Correct 351 ms 15676 KB Output is correct
41 Correct 218 ms 15264 KB Output is correct
42 Correct 158 ms 14340 KB Output is correct
43 Correct 592 ms 19408 KB Output is correct
44 Correct 606 ms 19412 KB Output is correct
45 Correct 615 ms 19288 KB Output is correct
46 Correct 321 ms 17048 KB Output is correct
47 Correct 483 ms 17828 KB Output is correct
48 Correct 221 ms 14544 KB Output is correct
49 Correct 620 ms 19260 KB Output is correct
50 Correct 577 ms 19316 KB Output is correct
51 Correct 577 ms 19156 KB Output is correct
52 Correct 410 ms 17688 KB Output is correct
53 Correct 239 ms 16140 KB Output is correct