oj.uz

Submission #670576

# Submission time Handle Problem Language Result Execution time Memory
670576 2022-12-09T14:54:28 Z bojackduy Examination (JOI19_examination) C++14
43 / 100
 3000 ms 463904 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#include <assert.h>
#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;
const int B = 700;


int n, m, sz, numB;

#define get_id(x) (x + B - 1) / B
#define lef(x) (x - 1) * B + 1
#define rig(x) min(x * B, sz)

int idex[N];
array<int, 3> a[N];
int block[N / B + 10][N], ans[N];
vi store[N], bit[N];
void quick_sort(int l, int r) {
    int i = l, j = r, x = a[l + r >> 1][2];
    while (i <= j) {
        while (a[i][2] > x) i++;
        while (a[j][2] < x) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            swap(idex[i], idex[j]);
            i++, j--;
        }
    }
    if (l < j) quick_sort(l, j);
    if (i < r) quick_sort(i, r);
}

void upd(int id, int x) {
    for (; x > 0 ; x -= x & -x) block[id][x]++;
}
int get(int id, int x) {
    int sum = 0;
    for (; x <= sz; x += x & -x) sum += block[id][x];
return sum;
}

void upd1(int id, int x) {
    for (; x > 0; x -= x & -x) bit[id][x]++;
}
int get1(int id, int x) {
    int sum = 0;
    for (; x < bit[id].size(); x += x & -x) sum += bit[id][x];
return sum;
}

void adj(int i) {
    int id = get_id(a[i][0]);
    upd(id, a[i][1]);
    int z = lower_bound(all(store[a[i][0]]), a[i][1]) - store[a[i][0]].begin() + 1;
    upd1(a[i][0], z);
}
int query(int i) {
    int res = 0;
    int id = get_id(a[i][0]);
    if (lef(id) != a[i][0]) id++;
    for (int j = id; j <= numB; j++) {
        res += get(j, a[i][1]);
    }
    if (lef(get_id(a[i][0])) != a[i][0]) {
        id = get_id(a[i][0]);
        for (int j = a[i][0]; j <= rig(id); j++) {
            int z = lower_bound(all(store[j]), a[i][1]) - store[j].begin() + 1;
            res += get1(j, z);
        }
    }
return res;
}

void solve(int test = -1) {
    cin >> n >> m;
    vector<array<int, 3>> b;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = a[i][0] + a[i][1];
        b.pb({a[i][0], i, 0});
        b.pb({a[i][1], i, 1});
        b.pb({a[i][2], i, 2});
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i + n][0] >> a[i + n][1] >> a[i + n][2];
        idex[i + n] = i;
        b.pb({a[i + n][0], i + n, 0});
        b.pb({a[i + n][1], i + n, 1});
        b.pb({a[i + n][2], i + n, 2});
    }
    sort(all(b));
    for (int i = 0; i < b.size(); i++) {
        if (i == 0 || b[i][0] != b[i - 1][0]) sz++;
        a[b[i][1]][b[i][2]] = sz;
    }
    numB = get_id(sz);

    for (int i = 1; i <= n; i++) {
        store[a[i][0]].pb(a[i][1]);
    }
    for (int i = 1; i <= sz; i++) {
        sort(all(store[i]));
        bit[i].resize(store[i].size() + 10);
    }

    sort(a + 1, a + 1 + n, [&](const array<int, 3> &x, const array<int, 3> &y) {
        return x[2] > y[2];
    });
    quick_sort(n + 1, n + m);
    int j = 1;
    for (int i = 1; i <= m; i++) {
        while (j <= n && a[j][2] >= a[i + n][2]) {
            adj(j);
            j++;
        }
        ans[idex[i + n]] = query(i + n);
    }
    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 'void quick_sort(int, int)':
examination.cpp:57:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int i = l, j = r, x = a[l + r >> 1][2];
      |                             ~~^~~
examination.cpp: In function 'int get1(int, int)':
examination.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   85 |     for (; x < bit[id].size(); x += x & -x) sum += bit[id][x];
      |              ^
examination.cpp: In function 'void solve(int)':
examination.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  130 |     for (int i = 0; i < b.size(); i++) {
      |                       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28416 KB Output is correct
3 Correct 16 ms 28448 KB Output is correct
4 Correct 15 ms 28488 KB Output is correct
5 Correct 15 ms 28480 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 34 ms 31244 KB Output is correct
8 Correct 34 ms 31288 KB Output is correct
9 Correct 36 ms 31176 KB Output is correct
10 Correct 32 ms 29592 KB Output is correct
11 Correct 33 ms 29464 KB Output is correct
12 Correct 21 ms 29088 KB Output is correct
13 Correct 33 ms 30872 KB Output is correct
14 Correct 32 ms 30888 KB Output is correct
15 Correct 32 ms 30800 KB Output is correct
16 Correct 27 ms 29136 KB Output is correct
17 Correct 32 ms 29452 KB Output is correct
18 Correct 19 ms 29040 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1858 ms 104780 KB Output is correct
2 Correct 1864 ms 104564 KB Output is correct
3 Correct 1849 ms 104604 KB Output is correct
4 Correct 1154 ms 47928 KB Output is correct
5 Correct 931 ms 45784 KB Output is correct
6 Correct 218 ms 43212 KB Output is correct
7 Correct 2000 ms 102760 KB Output is correct
8 Correct 1734 ms 102872 KB Output is correct
9 Correct 1602 ms 98056 KB Output is correct
10 Correct 682 ms 44816 KB Output is correct
11 Correct 1044 ms 47392 KB Output is correct
12 Correct 160 ms 43168 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1858 ms 104780 KB Output is correct
2 Correct 1864 ms 104564 KB Output is correct
3 Correct 1849 ms 104604 KB Output is correct
4 Correct 1154 ms 47928 KB Output is correct
5 Correct 931 ms 45784 KB Output is correct
6 Correct 218 ms 43212 KB Output is correct
7 Correct 2000 ms 102760 KB Output is correct
8 Correct 1734 ms 102872 KB Output is correct
9 Correct 1602 ms 98056 KB Output is correct
10 Correct 682 ms 44816 KB Output is correct
11 Correct 1044 ms 47392 KB Output is correct
12 Correct 160 ms 43168 KB Output is correct
13 Correct 1999 ms 106276 KB Output is correct
14 Correct 1892 ms 105700 KB Output is correct
15 Correct 1869 ms 104556 KB Output is correct
16 Correct 1176 ms 48012 KB Output is correct
17 Correct 967 ms 45888 KB Output is correct
18 Correct 216 ms 43252 KB Output is correct
19 Correct 1971 ms 106544 KB Output is correct
20 Correct 2012 ms 105628 KB Output is correct
21 Correct 1993 ms 104752 KB Output is correct
22 Correct 686 ms 44828 KB Output is correct
23 Correct 1064 ms 47148 KB Output is correct
24 Correct 172 ms 43272 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28416 KB Output is correct
3 Correct 16 ms 28448 KB Output is correct
4 Correct 15 ms 28488 KB Output is correct
5 Correct 15 ms 28480 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 34 ms 31244 KB Output is correct
8 Correct 34 ms 31288 KB Output is correct
9 Correct 36 ms 31176 KB Output is correct
10 Correct 32 ms 29592 KB Output is correct
11 Correct 33 ms 29464 KB Output is correct
12 Correct 21 ms 29088 KB Output is correct
13 Correct 33 ms 30872 KB Output is correct
14 Correct 32 ms 30888 KB Output is correct
15 Correct 32 ms 30800 KB Output is correct
16 Correct 27 ms 29136 KB Output is correct
17 Correct 32 ms 29452 KB Output is correct
18 Correct 19 ms 29040 KB Output is correct
19 Correct 1858 ms 104780 KB Output is correct
20 Correct 1864 ms 104564 KB Output is correct
21 Correct 1849 ms 104604 KB Output is correct
22 Correct 1154 ms 47928 KB Output is correct
23 Correct 931 ms 45784 KB Output is correct
24 Correct 218 ms 43212 KB Output is correct
25 Correct 2000 ms 102760 KB Output is correct
26 Correct 1734 ms 102872 KB Output is correct
27 Correct 1602 ms 98056 KB Output is correct
28 Correct 682 ms 44816 KB Output is correct
29 Correct 1044 ms 47392 KB Output is correct
30 Correct 160 ms 43168 KB Output is correct
31 Correct 1999 ms 106276 KB Output is correct
32 Correct 1892 ms 105700 KB Output is correct
33 Correct 1869 ms 104556 KB Output is correct
34 Correct 1176 ms 48012 KB Output is correct
35 Correct 967 ms 45888 KB Output is correct
36 Correct 216 ms 43252 KB Output is correct
37 Correct 1971 ms 106544 KB Output is correct
38 Correct 2012 ms 105628 KB Output is correct
39 Correct 1993 ms 104752 KB Output is correct
40 Correct 686 ms 44828 KB Output is correct
41 Correct 1064 ms 47148 KB Output is correct
42 Correct 172 ms 43272 KB Output is correct
43 Execution timed out 3103 ms 463904 KB Time limit exceeded
44 Halted 0 ms 0 KB -