oj.uz

답안 #670589

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670589 2022-12-09T15:48:39 Z bojackduy Examination (JOI19_examination) C++14
43 / 100
 3000 ms 597412 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

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 14 ms 28644 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Correct 15 ms 28452 KB Output is correct
5 Correct 13 ms 28556 KB Output is correct
6 Correct 13 ms 28460 KB Output is correct
7 Correct 23 ms 30060 KB Output is correct
8 Correct 23 ms 30144 KB Output is correct
9 Correct 22 ms 30032 KB Output is correct
10 Correct 21 ms 29104 KB Output is correct
11 Correct 21 ms 29136 KB Output is correct
12 Correct 17 ms 29056 KB Output is correct
13 Correct 22 ms 29904 KB Output is correct
14 Correct 22 ms 29880 KB Output is correct
15 Correct 22 ms 29868 KB Output is correct
16 Correct 19 ms 29120 KB Output is correct
17 Correct 21 ms 29136 KB Output is correct
18 Correct 17 ms 29076 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1535 ms 82868 KB Output is correct
2 Correct 1361 ms 83100 KB Output is correct
3 Correct 1518 ms 83064 KB Output is correct
4 Correct 906 ms 44452 KB Output is correct
5 Correct 436 ms 43304 KB Output is correct
6 Correct 164 ms 43216 KB Output is correct
7 Correct 1511 ms 81880 KB Output is correct
8 Correct 1272 ms 82000 KB Output is correct
9 Correct 1118 ms 78744 KB Output is correct
10 Correct 331 ms 43236 KB Output is correct
11 Correct 681 ms 44064 KB Output is correct
12 Correct 119 ms 43312 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1535 ms 82868 KB Output is correct
2 Correct 1361 ms 83100 KB Output is correct
3 Correct 1518 ms 83064 KB Output is correct
4 Correct 906 ms 44452 KB Output is correct
5 Correct 436 ms 43304 KB Output is correct
6 Correct 164 ms 43216 KB Output is correct
7 Correct 1511 ms 81880 KB Output is correct
8 Correct 1272 ms 82000 KB Output is correct
9 Correct 1118 ms 78744 KB Output is correct
10 Correct 331 ms 43236 KB Output is correct
11 Correct 681 ms 44064 KB Output is correct
12 Correct 119 ms 43312 KB Output is correct
13 Correct 1457 ms 83836 KB Output is correct
14 Correct 1453 ms 83780 KB Output is correct
15 Correct 1337 ms 82944 KB Output is correct
16 Correct 952 ms 44516 KB Output is correct
17 Correct 455 ms 43216 KB Output is correct
18 Correct 173 ms 43436 KB Output is correct
19 Correct 1416 ms 83780 KB Output is correct
20 Correct 1439 ms 83656 KB Output is correct
21 Correct 1406 ms 82672 KB Output is correct
22 Correct 330 ms 43320 KB Output is correct
23 Correct 802 ms 44032 KB Output is correct
24 Correct 121 ms 43316 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 14 ms 28644 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Correct 15 ms 28452 KB Output is correct
5 Correct 13 ms 28556 KB Output is correct
6 Correct 13 ms 28460 KB Output is correct
7 Correct 23 ms 30060 KB Output is correct
8 Correct 23 ms 30144 KB Output is correct
9 Correct 22 ms 30032 KB Output is correct
10 Correct 21 ms 29104 KB Output is correct
11 Correct 21 ms 29136 KB Output is correct
12 Correct 17 ms 29056 KB Output is correct
13 Correct 22 ms 29904 KB Output is correct
14 Correct 22 ms 29880 KB Output is correct
15 Correct 22 ms 29868 KB Output is correct
16 Correct 19 ms 29120 KB Output is correct
17 Correct 21 ms 29136 KB Output is correct
18 Correct 17 ms 29076 KB Output is correct
19 Correct 1535 ms 82868 KB Output is correct
20 Correct 1361 ms 83100 KB Output is correct
21 Correct 1518 ms 83064 KB Output is correct
22 Correct 906 ms 44452 KB Output is correct
23 Correct 436 ms 43304 KB Output is correct
24 Correct 164 ms 43216 KB Output is correct
25 Correct 1511 ms 81880 KB Output is correct
26 Correct 1272 ms 82000 KB Output is correct
27 Correct 1118 ms 78744 KB Output is correct
28 Correct 331 ms 43236 KB Output is correct
29 Correct 681 ms 44064 KB Output is correct
30 Correct 119 ms 43312 KB Output is correct
31 Correct 1457 ms 83836 KB Output is correct
32 Correct 1453 ms 83780 KB Output is correct
33 Correct 1337 ms 82944 KB Output is correct
34 Correct 952 ms 44516 KB Output is correct
35 Correct 455 ms 43216 KB Output is correct
36 Correct 173 ms 43436 KB Output is correct
37 Correct 1416 ms 83780 KB Output is correct
38 Correct 1439 ms 83656 KB Output is correct
39 Correct 1406 ms 82672 KB Output is correct
40 Correct 330 ms 43320 KB Output is correct
41 Correct 802 ms 44032 KB Output is correct
42 Correct 121 ms 43316 KB Output is correct
43 Execution timed out 3101 ms 597412 KB Time limit exceeded
44 Halted 0 ms 0 KB -