oj.uz

Submission #557298

# Submission time Handle Problem Language Result Execution time Memory
557298 2022-05-05T05:49:23 Z Ai7081 Examination (JOI19_examination) C++17
100 / 100
 2113 ms 126204 KB 
#include <bits/stdc++.h>
using namespace std;
const bool debug = 0;

const int N = 1e5 + 5;

struct query{
    int x, y, z, idx;
    bool operator < (const query &o) const {return z > o.z;}
};

struct score{
    int a, b;
    bool operator < (const score &o) const {return a+b > o.a+o.b;}
};

int n, t, fenA[N], fenB[N], timer, now, ans[N];
score s[N];
query q[N];
vector<int> fen[N];
set<int> fen_st[N], A, B;
map<int, int> mpA, mpB, mp_fen[N];

void add_set(int i, int val) {
    for (; i<N; i+=i&(-i)) fen_st[i].insert(val);
}

void add(int idx) {
    int i = mpA[s[idx].a];
    for (; i<=A.size(); i+=i&(-i)) {
        fenA[i]++;
        int j = mp_fen[i][s[idx].b];
        if (debug) printf("add %d %d\n", i, j);
        for (; j<=mp_fen[i].size(); j+=j&(-j)) fen[i][j]++;
    }
    if (debug) printf("add 1&2\n");
    i = mpB[s[idx].b];
    for (; i<=B.size(); i+=i&(-i)) fenB[i]++;
}

int query(int x, int y) {
    int ret = now;
    if (debug) printf("query now = %d\n", ret);
    auto it = mpA.lower_bound(x);
    if (it != mpA.begin()) {
        int i = mpA[(--it)->first];
        for (; i>0; i-=i&(-i)) {
            ret -= fenA[i];
            if (debug) printf("query - fenA[%d] = %d\n", i, ret);
            it = mp_fen[i].lower_bound(y);
            if (it != mp_fen[i].begin()) {
                int j = mp_fen[i][(--it)->first];
                for (; j>0; j-=j&(-j)) ret += fen[i][j];
                if (debug) printf("qeury %d %d = %d\n", i, j, ret);
            }
        }
    }
    it = mpB.lower_bound(y);
    if (it != mpB.begin()) {
        int i = mpB[(--it)->first];
        for (; i>0; i-=i&(-i)) ret -= fenB[i];
        if (debug) printf("query -fenB = %d\n", ret);
    }
    return ret;
}

int main() {
    scanf(" %d %d", &n, &t);
    for (int i=0; i<n; i++) scanf(" %d %d", &s[i].a, &s[i].b);
    for (int i=0; i<t; i++) scanf(" %d %d %d", &q[i].x, &q[i].y, &q[i].z), q[i].idx = i;
    sort(s, s+n);
    sort(q, q+t);
    if (debug) {
        printf("sorted score\n");
        for (int i=0; i<n; i++) printf("a %d b %d\n", s[i].a, s[i].b);
        printf("sorted query\n");
        for (int i=0; i<t; i++) printf("x %d y %d z %d idx %d\n", q[i].x, q[i].y, q[i].z, q[i].idx);
    }

    // build fenwick tree
    for (int i=0; i<n; i++) A.insert(s[i].a), B.insert(s[i].b);
    timer = 0;
    for (auto it : A) mpA[it] = ++timer;
    timer = 0 ;
    for (auto it : B) mpB[it] = ++timer;
    if (debug) {
        printf("mpA : ");
        for (auto [key,val] : mpA) printf("(%d %d) ", key, val);
        printf("\n");
        printf("mpB : ");
        for (auto [key,val] : mpB) printf("(%d %d) ", key, val);
        printf("\n");
    }
    for (int i=0; i<n; i++) add_set(mpA[s[i].a], s[i].b);
    if (debug) {
        for (int i=1; i<=n; i++) {
            printf("fen_st %d : ", i);
            for (auto it : fen_st[i]) printf("%d ", it);
            printf("\n");
        }
        printf("\t\tadd_set done\n");
    }
    for (int i=1; i<=mpA.size(); i++) {
        fen[i].assign(fen_st[i].size()+5, 0);
        timer = 0;
        for (auto it : fen_st[i]) mp_fen[i][it] = ++timer;
    }
    if (debug) {
        printf("\t\tbuild map and assign fenwick done\n");
    }

    // do query
    for (int i=0; i<t; i++) {
        while (now < n && s[now].a + s[now].b >= q[i].z) add(now++);
        if (debug) printf("\t\tadd for t = %d done\n", i);
        ans[q[i].idx] = query(q[i].x, q[i].y);
        if (debug) printf("\t\tquery for t = %d done\n", i);
        if (debug) printf("\t\tans %d : %d\n", q[i].idx, ans[q[i].idx]);
    }
    if (debug) printf("all done next is answer\n");
    for (int i=0; i<n; i++) printf("%d\n", ans[i]);
    return 0;
}

Compilation message

examination.cpp: In function 'void add(int)':
examination.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (; i<=A.size(); i+=i&(-i)) {
      |            ~^~~~~~~~~~
examination.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (; j<=mp_fen[i].size(); j+=j&(-j)) fen[i][j]++;
      |                ~^~~~~~~~~~~~~~~~~~
examination.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (; i<=B.size(); i+=i&(-i)) fenB[i]++;
      |            ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i=1; i<=mpA.size(); i++) {
      |                   ~^~~~~~~~~~~~
examination.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf(" %d %d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:69:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     for (int i=0; i<n; i++) scanf(" %d %d", &s[i].a, &s[i].b);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:70:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     for (int i=0; i<t; i++) scanf(" %d %d %d", &q[i].x, &q[i].y, &q[i].z), q[i].idx = i;
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 9 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 12068 KB Output is correct
5 Correct 6 ms 12040 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 24 ms 15388 KB Output is correct
8 Correct 24 ms 15436 KB Output is correct
9 Correct 26 ms 15400 KB Output is correct
10 Correct 14 ms 13296 KB Output is correct
11 Correct 23 ms 15012 KB Output is correct
12 Correct 12 ms 12192 KB Output is correct
13 Correct 32 ms 15464 KB Output is correct
14 Correct 30 ms 15480 KB Output is correct
15 Correct 24 ms 15384 KB Output is correct
16 Correct 17 ms 15060 KB Output is correct
17 Correct 12 ms 12828 KB Output is correct
18 Correct 8 ms 12116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1841 ms 111556 KB Output is correct
2 Correct 1749 ms 111500 KB Output is correct
3 Correct 1740 ms 111788 KB Output is correct
4 Correct 294 ms 45100 KB Output is correct
5 Correct 816 ms 80960 KB Output is correct
6 Correct 98 ms 16292 KB Output is correct
7 Correct 1311 ms 111696 KB Output is correct
8 Correct 1529 ms 111632 KB Output is correct
9 Correct 1247 ms 111576 KB Output is correct
10 Correct 563 ms 76796 KB Output is correct
11 Correct 206 ms 31040 KB Output is correct
12 Correct 80 ms 15980 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1841 ms 111556 KB Output is correct
2 Correct 1749 ms 111500 KB Output is correct
3 Correct 1740 ms 111788 KB Output is correct
4 Correct 294 ms 45100 KB Output is correct
5 Correct 816 ms 80960 KB Output is correct
6 Correct 98 ms 16292 KB Output is correct
7 Correct 1311 ms 111696 KB Output is correct
8 Correct 1529 ms 111632 KB Output is correct
9 Correct 1247 ms 111576 KB Output is correct
10 Correct 563 ms 76796 KB Output is correct
11 Correct 206 ms 31040 KB Output is correct
12 Correct 80 ms 15980 KB Output is correct
13 Correct 1898 ms 111712 KB Output is correct
14 Correct 1883 ms 111532 KB Output is correct
15 Correct 1798 ms 111540 KB Output is correct
16 Correct 334 ms 45464 KB Output is correct
17 Correct 815 ms 81368 KB Output is correct
18 Correct 88 ms 16428 KB Output is correct
19 Correct 1941 ms 111572 KB Output is correct
20 Correct 1931 ms 111656 KB Output is correct
21 Correct 1765 ms 111604 KB Output is correct
22 Correct 531 ms 76876 KB Output is correct
23 Correct 213 ms 30920 KB Output is correct
24 Correct 83 ms 15944 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 9 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 12068 KB Output is correct
5 Correct 6 ms 12040 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 24 ms 15388 KB Output is correct
8 Correct 24 ms 15436 KB Output is correct
9 Correct 26 ms 15400 KB Output is correct
10 Correct 14 ms 13296 KB Output is correct
11 Correct 23 ms 15012 KB Output is correct
12 Correct 12 ms 12192 KB Output is correct
13 Correct 32 ms 15464 KB Output is correct
14 Correct 30 ms 15480 KB Output is correct
15 Correct 24 ms 15384 KB Output is correct
16 Correct 17 ms 15060 KB Output is correct
17 Correct 12 ms 12828 KB Output is correct
18 Correct 8 ms 12116 KB Output is correct
19 Correct 1841 ms 111556 KB Output is correct
20 Correct 1749 ms 111500 KB Output is correct
21 Correct 1740 ms 111788 KB Output is correct
22 Correct 294 ms 45100 KB Output is correct
23 Correct 816 ms 80960 KB Output is correct
24 Correct 98 ms 16292 KB Output is correct
25 Correct 1311 ms 111696 KB Output is correct
26 Correct 1529 ms 111632 KB Output is correct
27 Correct 1247 ms 111576 KB Output is correct
28 Correct 563 ms 76796 KB Output is correct
29 Correct 206 ms 31040 KB Output is correct
30 Correct 80 ms 15980 KB Output is correct
31 Correct 1898 ms 111712 KB Output is correct
32 Correct 1883 ms 111532 KB Output is correct
33 Correct 1798 ms 111540 KB Output is correct
34 Correct 334 ms 45464 KB Output is correct
35 Correct 815 ms 81368 KB Output is correct
36 Correct 88 ms 16428 KB Output is correct
37 Correct 1941 ms 111572 KB Output is correct
38 Correct 1931 ms 111656 KB Output is correct
39 Correct 1765 ms 111604 KB Output is correct
40 Correct 531 ms 76876 KB Output is correct
41 Correct 213 ms 30920 KB Output is correct
42 Correct 83 ms 15944 KB Output is correct
43 Correct 2113 ms 126148 KB Output is correct
44 Correct 2092 ms 126204 KB Output is correct
45 Correct 2090 ms 126020 KB Output is correct
46 Correct 383 ms 53600 KB Output is correct
47 Correct 998 ms 110908 KB Output is correct
48 Correct 88 ms 16100 KB Output is correct
49 Correct 1596 ms 126024 KB Output is correct
50 Correct 1788 ms 125952 KB Output is correct
51 Correct 1564 ms 126172 KB Output is correct
52 Correct 690 ms 111984 KB Output is correct
53 Correct 252 ms 39464 KB Output is correct