oj.uz

Submission #471332

# Submission time Handle Problem Language Result Execution time Memory
471332 2021-09-08T12:57:18 Z spike1236 Examination (JOI19_examination) C++14
100 / 100
 1883 ms 67248 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 = 2e5 + 10;
pair <int, int> a[MAXN];
map <int, vector <vector <int> > > q;
vector <int> fw[MAXN], comp, comp2[MAXN];
int ans[MAXN];

int get_a(int v) {
    return lower_bound(comp.begin(), comp.end(), v) - comp.begin() + 1;
}

int get_b(int x, int y) {
    return lower_bound(comp2[x].begin(), comp2[x].end(), y) - comp2[x].begin() + 1;
}

void pre_upd(int x, int y) {
    for(int i = get_a(x); i <= comp.size(); i += i & -i) comp2[i].push_back(y);
}

void pre_get(int x, int y) {
    for(int i = get_a(x); i > 0; i -= i & -i) comp2[i].push_back(y);
}

void upd(int x, int y, int val) {
    for(int i = get_a(x); i <= comp.size(); i += i & -i)
        for(int j = get_b(i, y); j <= comp2[i].size(); j += j & -j)
            fw[i][j] += val;
}

int get(int x, int y) {
    int res = 0;
    for(int i = get_a(x); i > 0; i -= i & -i) {
        for(int j = get_b(i, y); j > 0; j -= j & -j) {
            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;
        comp.push_back(a[i].f);
    }
    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});
        comp.push_back(x - 1);
    }
    comp.push_back(1e9);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for(int i = 0; i < n; ++i) pre_upd(a[i].f, a[i].s);
    for(auto &it : q) {
        for(auto &j : it.s) {
            pre_get(j[0] - 1, j[1] - 1);
            pre_get(j[0] - 1, 1e9);
            pre_get(1e9, j[1] - 1);
        }
    }
    for(int i = 1; i <= comp.size(); ++i) {
        sort(comp2[i].begin(), comp2[i].end());
        comp2[i].erase(unique(comp2[i].begin(), comp2[i].end()), comp2[i].end());
        fw[i].resize(comp2[i].size() + 1);
    }
    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;
}

Compilation message

examination.cpp: In function 'void pre_upd(int, int)':
examination.cpp:27:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = get_a(x); i <= comp.size(); i += i & -i) comp2[i].push_back(y);
      |                           ~~^~~~~~~~~~~~~~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = get_a(x); i <= comp.size(); i += i & -i)
      |                           ~~^~~~~~~~~~~~~~
examination.cpp:36:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j = get_b(i, y); j <= comp2[i].size(); j += j & -j)
      |                                  ~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 1; i <= comp.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9592 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9600 KB Output is correct
7 Correct 31 ms 11024 KB Output is correct
8 Correct 30 ms 11092 KB Output is correct
9 Correct 30 ms 11028 KB Output is correct
10 Correct 22 ms 10912 KB Output is correct
11 Correct 18 ms 10444 KB Output is correct
12 Correct 12 ms 10092 KB Output is correct
13 Correct 27 ms 11084 KB Output is correct
14 Correct 26 ms 11036 KB Output is correct
15 Correct 26 ms 11032 KB Output is correct
16 Correct 14 ms 10188 KB Output is correct
17 Correct 20 ms 10996 KB Output is correct
18 Correct 11 ms 10060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 50212 KB Output is correct
2 Correct 1096 ms 51396 KB Output is correct
3 Correct 1191 ms 53396 KB Output is correct
4 Correct 505 ms 43128 KB Output is correct
5 Correct 358 ms 29760 KB Output is correct
6 Correct 197 ms 27328 KB Output is correct
7 Correct 804 ms 47068 KB Output is correct
8 Correct 986 ms 49532 KB Output is correct
9 Correct 835 ms 47912 KB Output is correct
10 Correct 270 ms 27200 KB Output is correct
11 Correct 446 ms 43684 KB Output is correct
12 Correct 173 ms 26280 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 50212 KB Output is correct
2 Correct 1096 ms 51396 KB Output is correct
3 Correct 1191 ms 53396 KB Output is correct
4 Correct 505 ms 43128 KB Output is correct
5 Correct 358 ms 29760 KB Output is correct
6 Correct 197 ms 27328 KB Output is correct
7 Correct 804 ms 47068 KB Output is correct
8 Correct 986 ms 49532 KB Output is correct
9 Correct 835 ms 47912 KB Output is correct
10 Correct 270 ms 27200 KB Output is correct
11 Correct 446 ms 43684 KB Output is correct
12 Correct 173 ms 26280 KB Output is correct
13 Correct 1447 ms 53216 KB Output is correct
14 Correct 1319 ms 51900 KB Output is correct
15 Correct 1073 ms 50076 KB Output is correct
16 Correct 651 ms 44984 KB Output is correct
17 Correct 515 ms 31296 KB Output is correct
18 Correct 210 ms 24500 KB Output is correct
19 Correct 1482 ms 54612 KB Output is correct
20 Correct 1491 ms 53372 KB Output is correct
21 Correct 1526 ms 54172 KB Output is correct
22 Correct 289 ms 27000 KB Output is correct
23 Correct 489 ms 43976 KB Output is correct
24 Correct 175 ms 26172 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9592 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9600 KB Output is correct
7 Correct 31 ms 11024 KB Output is correct
8 Correct 30 ms 11092 KB Output is correct
9 Correct 30 ms 11028 KB Output is correct
10 Correct 22 ms 10912 KB Output is correct
11 Correct 18 ms 10444 KB Output is correct
12 Correct 12 ms 10092 KB Output is correct
13 Correct 27 ms 11084 KB Output is correct
14 Correct 26 ms 11036 KB Output is correct
15 Correct 26 ms 11032 KB Output is correct
16 Correct 14 ms 10188 KB Output is correct
17 Correct 20 ms 10996 KB Output is correct
18 Correct 11 ms 10060 KB Output is correct
19 Correct 1170 ms 50212 KB Output is correct
20 Correct 1096 ms 51396 KB Output is correct
21 Correct 1191 ms 53396 KB Output is correct
22 Correct 505 ms 43128 KB Output is correct
23 Correct 358 ms 29760 KB Output is correct
24 Correct 197 ms 27328 KB Output is correct
25 Correct 804 ms 47068 KB Output is correct
26 Correct 986 ms 49532 KB Output is correct
27 Correct 835 ms 47912 KB Output is correct
28 Correct 270 ms 27200 KB Output is correct
29 Correct 446 ms 43684 KB Output is correct
30 Correct 173 ms 26280 KB Output is correct
31 Correct 1447 ms 53216 KB Output is correct
32 Correct 1319 ms 51900 KB Output is correct
33 Correct 1073 ms 50076 KB Output is correct
34 Correct 651 ms 44984 KB Output is correct
35 Correct 515 ms 31296 KB Output is correct
36 Correct 210 ms 24500 KB Output is correct
37 Correct 1482 ms 54612 KB Output is correct
38 Correct 1491 ms 53372 KB Output is correct
39 Correct 1526 ms 54172 KB Output is correct
40 Correct 289 ms 27000 KB Output is correct
41 Correct 489 ms 43976 KB Output is correct
42 Correct 175 ms 26172 KB Output is correct
43 Correct 1770 ms 66540 KB Output is correct
44 Correct 1839 ms 67188 KB Output is correct
45 Correct 1775 ms 67248 KB Output is correct
46 Correct 830 ms 56792 KB Output is correct
47 Correct 603 ms 36284 KB Output is correct
48 Correct 222 ms 23716 KB Output is correct
49 Correct 1591 ms 64896 KB Output is correct
50 Correct 1883 ms 66388 KB Output is correct
51 Correct 1452 ms 62284 KB Output is correct
52 Correct 448 ms 32900 KB Output is correct
53 Correct 547 ms 51744 KB Output is correct