oj.uz

답안 #670577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670577 2022-12-09T14:55:46 Z bojackduy Examination (JOI19_examination) C++14
43 / 100
 3000 ms 543524 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];
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() + 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++) {
      |                       ^

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28452 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 15 ms 28420 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 15 ms 28524 KB Output is correct
7 Correct 33 ms 30376 KB Output is correct
8 Correct 35 ms 30416 KB Output is correct
9 Correct 35 ms 30364 KB Output is correct
10 Correct 34 ms 29348 KB Output is correct
11 Correct 30 ms 29304 KB Output is correct
12 Correct 19 ms 29076 KB Output is correct
13 Correct 31 ms 30124 KB Output is correct
14 Correct 32 ms 30200 KB Output is correct
15 Correct 35 ms 30152 KB Output is correct
16 Correct 25 ms 29096 KB Output is correct
17 Correct 31 ms 29164 KB Output is correct
18 Correct 19 ms 29056 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1596 ms 84932 KB Output is correct
2 Correct 1560 ms 84668 KB Output is correct
3 Correct 1614 ms 84660 KB Output is correct
4 Correct 1120 ms 45108 KB Output is correct
5 Correct 745 ms 43848 KB Output is correct
6 Correct 216 ms 43268 KB Output is correct
7 Correct 1766 ms 83672 KB Output is correct
8 Correct 1434 ms 83680 KB Output is correct
9 Correct 1173 ms 80024 KB Output is correct
10 Correct 536 ms 43292 KB Output is correct
11 Correct 868 ms 44504 KB Output is correct
12 Correct 166 ms 43268 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1596 ms 84932 KB Output is correct
2 Correct 1560 ms 84668 KB Output is correct
3 Correct 1614 ms 84660 KB Output is correct
4 Correct 1120 ms 45108 KB Output is correct
5 Correct 745 ms 43848 KB Output is correct
6 Correct 216 ms 43268 KB Output is correct
7 Correct 1766 ms 83672 KB Output is correct
8 Correct 1434 ms 83680 KB Output is correct
9 Correct 1173 ms 80024 KB Output is correct
10 Correct 536 ms 43292 KB Output is correct
11 Correct 868 ms 44504 KB Output is correct
12 Correct 166 ms 43268 KB Output is correct
13 Correct 1798 ms 86008 KB Output is correct
14 Correct 1697 ms 85388 KB Output is correct
15 Correct 1676 ms 84640 KB Output is correct
16 Correct 1128 ms 45244 KB Output is correct
17 Correct 781 ms 43976 KB Output is correct
18 Correct 220 ms 43184 KB Output is correct
19 Correct 1645 ms 86092 KB Output is correct
20 Correct 1823 ms 85608 KB Output is correct
21 Correct 1684 ms 84740 KB Output is correct
22 Correct 537 ms 43212 KB Output is correct
23 Correct 933 ms 44460 KB Output is correct
24 Correct 161 ms 43232 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28452 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 15 ms 28420 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 15 ms 28524 KB Output is correct
7 Correct 33 ms 30376 KB Output is correct
8 Correct 35 ms 30416 KB Output is correct
9 Correct 35 ms 30364 KB Output is correct
10 Correct 34 ms 29348 KB Output is correct
11 Correct 30 ms 29304 KB Output is correct
12 Correct 19 ms 29076 KB Output is correct
13 Correct 31 ms 30124 KB Output is correct
14 Correct 32 ms 30200 KB Output is correct
15 Correct 35 ms 30152 KB Output is correct
16 Correct 25 ms 29096 KB Output is correct
17 Correct 31 ms 29164 KB Output is correct
18 Correct 19 ms 29056 KB Output is correct
19 Correct 1596 ms 84932 KB Output is correct
20 Correct 1560 ms 84668 KB Output is correct
21 Correct 1614 ms 84660 KB Output is correct
22 Correct 1120 ms 45108 KB Output is correct
23 Correct 745 ms 43848 KB Output is correct
24 Correct 216 ms 43268 KB Output is correct
25 Correct 1766 ms 83672 KB Output is correct
26 Correct 1434 ms 83680 KB Output is correct
27 Correct 1173 ms 80024 KB Output is correct
28 Correct 536 ms 43292 KB Output is correct
29 Correct 868 ms 44504 KB Output is correct
30 Correct 166 ms 43268 KB Output is correct
31 Correct 1798 ms 86008 KB Output is correct
32 Correct 1697 ms 85388 KB Output is correct
33 Correct 1676 ms 84640 KB Output is correct
34 Correct 1128 ms 45244 KB Output is correct
35 Correct 781 ms 43976 KB Output is correct
36 Correct 220 ms 43184 KB Output is correct
37 Correct 1645 ms 86092 KB Output is correct
38 Correct 1823 ms 85608 KB Output is correct
39 Correct 1684 ms 84740 KB Output is correct
40 Correct 537 ms 43212 KB Output is correct
41 Correct 933 ms 44460 KB Output is correct
42 Correct 161 ms 43232 KB Output is correct
43 Execution timed out 3122 ms 543524 KB Time limit exceeded
44 Halted 0 ms 0 KB -