oj.uz

Submission #670600

# Submission time Handle Problem Language Result Execution time Memory
670600 2022-12-09T16:32:49 Z bojackduy Examination (JOI19_examination) C++14
100 / 100
 828 ms 66372 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#include <numeric>
#define task "task"
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (y < x) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}

const int N = 6e5 + 10;



int n, m, sz;


array<int, 3> a[N];
int ans[N];
vi store[N], v;
vector<vi> bit;

void adj(int x, int y) {
    x = lower_bound(all(v), x) - v.begin() + 1;
    for (;x > 0; x -= x & -x) {
        int i = lower_bound(all(store[x]), y) - store[x].begin() + 1;
        for (; i > 0; i -= i & -i) bit[x][i]++;
    }
}
int get(int x, int y) {
    int sum = 0;
    x = lower_bound(all(v), x) - v.begin() + 1;
    for (; x <= v.size(); x += x & -x) {
        int i = lower_bound(all(store[x]), y) - store[x].begin() + 1;
        for (; i <= store[x].size(); i += i & -i) sum += bit[x][i];
    }
return sum;
}
void solve(int test = -1) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = a[i][0] + a[i][1];
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i + n][0] >> a[i + n][1] >> a[i + n][2];
    }

    vi id(m);
    iota(all(id), 1);
    sort(a + 1, a + 1 + n, [&](const array<int, 3> &x, const array<int, 3> &y) {
        return x[2] > y[2];
    });
    sort(all(id), [&](const int &x, const int &y) {
        return a[x + n][2] > a[y + n][2];
    });

    for (int i = 1; i <= n + m; i++)
        v.pb(a[i][0]);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    bit.resize(v.size() + 2, vi(0));

    for (int i = 1; i <= n + m; i++) {
        int z = lower_bound(all(v), a[i][0]) - v.begin() + 1;
        for (int j = z; j <= v.size(); j += j & -j) store[j].pb(a[i][1]);
        for (int j = z; j > 0; j -= j & -j) store[j].pb(a[i][1]);
    }    
    for (int i = 1; i <= v.size(); i++) {
        sort(all(store[i]));
        store[i].erase(unique(all(store[i])), store[i].end());
        bit[i].resize(store[i].size() + 2);
    }


    int j = 1;
    for (int i: id) {
        while (j <= n && a[j][2] >= a[i + n][2]) {
            adj(a[j][0], a[j][1]);
            j++;
        }
        ans[i] = get(a[i + n][0], a[i + n][1]);
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
int32_t main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen(task".inp", "r", stdin);
    // freopen(task".out", "w", stdout);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}
/*

*/

Compilation message

examination.cpp: In function 'int get(int, int)':
examination.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   64 |     for (; x <= v.size(); x += x & -x) {
      |              ^
examination.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   66 |         for (; i <= store[x].size(); i += i & -i) sum += bit[x][i];
      |                  ^
examination.cpp: In function 'void solve(int)':
examination.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   97 |         for (int j = z; j <= v.size(); j += j & -j) store[j].pb(a[i][1]);
      |                           ^
examination.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  100 |     for (int i = 1; i <= v.size(); i++) {
      |                       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14336 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14344 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 19 ms 15536 KB Output is correct
8 Correct 18 ms 15444 KB Output is correct
9 Correct 18 ms 15496 KB Output is correct
10 Correct 15 ms 15240 KB Output is correct
11 Correct 15 ms 14676 KB Output is correct
12 Correct 11 ms 14676 KB Output is correct
13 Correct 18 ms 15444 KB Output is correct
14 Correct 18 ms 15512 KB Output is correct
15 Correct 22 ms 15536 KB Output is correct
16 Correct 10 ms 14676 KB Output is correct
17 Correct 14 ms 15192 KB Output is correct
18 Correct 9 ms 14676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 54004 KB Output is correct
2 Correct 614 ms 54216 KB Output is correct
3 Correct 609 ms 54132 KB Output is correct
4 Correct 318 ms 44656 KB Output is correct
5 Correct 162 ms 24340 KB Output is correct
6 Correct 88 ms 23700 KB Output is correct
7 Correct 590 ms 50064 KB Output is correct
8 Correct 615 ms 53636 KB Output is correct
9 Correct 545 ms 48956 KB Output is correct
10 Correct 127 ms 21524 KB Output is correct
11 Correct 252 ms 43632 KB Output is correct
12 Correct 70 ms 22340 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 54004 KB Output is correct
2 Correct 614 ms 54216 KB Output is correct
3 Correct 609 ms 54132 KB Output is correct
4 Correct 318 ms 44656 KB Output is correct
5 Correct 162 ms 24340 KB Output is correct
6 Correct 88 ms 23700 KB Output is correct
7 Correct 590 ms 50064 KB Output is correct
8 Correct 615 ms 53636 KB Output is correct
9 Correct 545 ms 48956 KB Output is correct
10 Correct 127 ms 21524 KB Output is correct
11 Correct 252 ms 43632 KB Output is correct
12 Correct 70 ms 22340 KB Output is correct
13 Correct 670 ms 54068 KB Output is correct
14 Correct 703 ms 54140 KB Output is correct
15 Correct 625 ms 54048 KB Output is correct
16 Correct 330 ms 44488 KB Output is correct
17 Correct 183 ms 24564 KB Output is correct
18 Correct 90 ms 23740 KB Output is correct
19 Correct 653 ms 54172 KB Output is correct
20 Correct 654 ms 54160 KB Output is correct
21 Correct 709 ms 50332 KB Output is correct
22 Correct 123 ms 21440 KB Output is correct
23 Correct 248 ms 43560 KB Output is correct
24 Correct 72 ms 22292 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14336 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14344 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 19 ms 15536 KB Output is correct
8 Correct 18 ms 15444 KB Output is correct
9 Correct 18 ms 15496 KB Output is correct
10 Correct 15 ms 15240 KB Output is correct
11 Correct 15 ms 14676 KB Output is correct
12 Correct 11 ms 14676 KB Output is correct
13 Correct 18 ms 15444 KB Output is correct
14 Correct 18 ms 15512 KB Output is correct
15 Correct 22 ms 15536 KB Output is correct
16 Correct 10 ms 14676 KB Output is correct
17 Correct 14 ms 15192 KB Output is correct
18 Correct 9 ms 14676 KB Output is correct
19 Correct 698 ms 54004 KB Output is correct
20 Correct 614 ms 54216 KB Output is correct
21 Correct 609 ms 54132 KB Output is correct
22 Correct 318 ms 44656 KB Output is correct
23 Correct 162 ms 24340 KB Output is correct
24 Correct 88 ms 23700 KB Output is correct
25 Correct 590 ms 50064 KB Output is correct
26 Correct 615 ms 53636 KB Output is correct
27 Correct 545 ms 48956 KB Output is correct
28 Correct 127 ms 21524 KB Output is correct
29 Correct 252 ms 43632 KB Output is correct
30 Correct 70 ms 22340 KB Output is correct
31 Correct 670 ms 54068 KB Output is correct
32 Correct 703 ms 54140 KB Output is correct
33 Correct 625 ms 54048 KB Output is correct
34 Correct 330 ms 44488 KB Output is correct
35 Correct 183 ms 24564 KB Output is correct
36 Correct 90 ms 23740 KB Output is correct
37 Correct 653 ms 54172 KB Output is correct
38 Correct 654 ms 54160 KB Output is correct
39 Correct 709 ms 50332 KB Output is correct
40 Correct 123 ms 21440 KB Output is correct
41 Correct 248 ms 43560 KB Output is correct
42 Correct 72 ms 22292 KB Output is correct
43 Correct 828 ms 61356 KB Output is correct
44 Correct 770 ms 65976 KB Output is correct
45 Correct 817 ms 66032 KB Output is correct
46 Correct 401 ms 53676 KB Output is correct
47 Correct 194 ms 28828 KB Output is correct
48 Correct 98 ms 24540 KB Output is correct
49 Correct 712 ms 66372 KB Output is correct
50 Correct 771 ms 65608 KB Output is correct
51 Correct 714 ms 66108 KB Output is correct
52 Correct 149 ms 25512 KB Output is correct
53 Correct 311 ms 51792 KB Output is correct