oj.uz

Submission #670582

# Submission time Handle Problem Language Result Execution time Memory
670582 2022-12-09T15:15:18 Z bojackduy Examination (JOI19_examination) C++14
43 / 100
 3000 ms 565408 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 = 1000;


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 + 1][N], ans[N], lab[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 = lab[j + 1]) {
            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]);
    }
    lab[sz + 1] = sz + 1;
    for (int i = sz; i >= 1; i--) {
        sort(all(store[i]));
        if (!store[i].size()) {
            lab[i] = lab[i + 1];
        continue;
        }
        lab[i] = i;
        bit[i].resize(store[i].size() + 1);
    }
    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++) {
      |                       ^
examination.cpp:9:23: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
    9 | #define size() size() * 1ll
      |                       ^
examination.cpp:142:23: note: in expansion of macro 'size'
  142 |         if (!store[i].size()) {
      |                       ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 14 ms 28536 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Correct 15 ms 28520 KB Output is correct
5 Correct 18 ms 28476 KB Output is correct
6 Correct 15 ms 28532 KB Output is correct
7 Correct 27 ms 30032 KB Output is correct
8 Correct 30 ms 30096 KB Output is correct
9 Correct 28 ms 30068 KB Output is correct
10 Correct 26 ms 29148 KB Output is correct
11 Correct 22 ms 29076 KB Output is correct
12 Correct 21 ms 29036 KB Output is correct
13 Correct 27 ms 29904 KB Output is correct
14 Correct 26 ms 29840 KB Output is correct
15 Correct 25 ms 29836 KB Output is correct
16 Correct 23 ms 29008 KB Output is correct
17 Correct 25 ms 29128 KB Output is correct
18 Correct 18 ms 29076 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 82804 KB Output is correct
2 Correct 1658 ms 82856 KB Output is correct
3 Correct 1605 ms 82828 KB Output is correct
4 Correct 1081 ms 44348 KB Output is correct
5 Correct 495 ms 43172 KB Output is correct
6 Correct 208 ms 43204 KB Output is correct
7 Correct 1616 ms 81888 KB Output is correct
8 Correct 1331 ms 81880 KB Output is correct
9 Correct 1335 ms 78432 KB Output is correct
10 Correct 407 ms 43204 KB Output is correct
11 Correct 890 ms 44120 KB Output is correct
12 Correct 165 ms 43284 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 82804 KB Output is correct
2 Correct 1658 ms 82856 KB Output is correct
3 Correct 1605 ms 82828 KB Output is correct
4 Correct 1081 ms 44348 KB Output is correct
5 Correct 495 ms 43172 KB Output is correct
6 Correct 208 ms 43204 KB Output is correct
7 Correct 1616 ms 81888 KB Output is correct
8 Correct 1331 ms 81880 KB Output is correct
9 Correct 1335 ms 78432 KB Output is correct
10 Correct 407 ms 43204 KB Output is correct
11 Correct 890 ms 44120 KB Output is correct
12 Correct 165 ms 43284 KB Output is correct
13 Correct 1631 ms 83628 KB Output is correct
14 Correct 1687 ms 83508 KB Output is correct
15 Correct 1659 ms 82800 KB Output is correct
16 Correct 1153 ms 44432 KB Output is correct
17 Correct 564 ms 43196 KB Output is correct
18 Correct 228 ms 43272 KB Output is correct
19 Correct 1725 ms 83656 KB Output is correct
20 Correct 1532 ms 83596 KB Output is correct
21 Correct 1731 ms 82412 KB Output is correct
22 Correct 433 ms 43180 KB Output is correct
23 Correct 865 ms 44084 KB Output is correct
24 Correct 158 ms 43180 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 14 ms 28536 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Correct 15 ms 28520 KB Output is correct
5 Correct 18 ms 28476 KB Output is correct
6 Correct 15 ms 28532 KB Output is correct
7 Correct 27 ms 30032 KB Output is correct
8 Correct 30 ms 30096 KB Output is correct
9 Correct 28 ms 30068 KB Output is correct
10 Correct 26 ms 29148 KB Output is correct
11 Correct 22 ms 29076 KB Output is correct
12 Correct 21 ms 29036 KB Output is correct
13 Correct 27 ms 29904 KB Output is correct
14 Correct 26 ms 29840 KB Output is correct
15 Correct 25 ms 29836 KB Output is correct
16 Correct 23 ms 29008 KB Output is correct
17 Correct 25 ms 29128 KB Output is correct
18 Correct 18 ms 29076 KB Output is correct
19 Correct 1668 ms 82804 KB Output is correct
20 Correct 1658 ms 82856 KB Output is correct
21 Correct 1605 ms 82828 KB Output is correct
22 Correct 1081 ms 44348 KB Output is correct
23 Correct 495 ms 43172 KB Output is correct
24 Correct 208 ms 43204 KB Output is correct
25 Correct 1616 ms 81888 KB Output is correct
26 Correct 1331 ms 81880 KB Output is correct
27 Correct 1335 ms 78432 KB Output is correct
28 Correct 407 ms 43204 KB Output is correct
29 Correct 890 ms 44120 KB Output is correct
30 Correct 165 ms 43284 KB Output is correct
31 Correct 1631 ms 83628 KB Output is correct
32 Correct 1687 ms 83508 KB Output is correct
33 Correct 1659 ms 82800 KB Output is correct
34 Correct 1153 ms 44432 KB Output is correct
35 Correct 564 ms 43196 KB Output is correct
36 Correct 228 ms 43272 KB Output is correct
37 Correct 1725 ms 83656 KB Output is correct
38 Correct 1532 ms 83596 KB Output is correct
39 Correct 1731 ms 82412 KB Output is correct
40 Correct 433 ms 43180 KB Output is correct
41 Correct 865 ms 44084 KB Output is correct
42 Correct 158 ms 43180 KB Output is correct
43 Execution timed out 3117 ms 565408 KB Time limit exceeded
44 Halted 0 ms 0 KB -