# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
737001 | 2023-05-06T12:23:27 Z | nguyentunglam | Advertisement 2 (JOI23_ho_t2) | C++17 | 223 ms | 14820 KB |
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 5e5 + 10; int x[N], e[N], n; vector<pair<int, int> > v; struct BIT { int bit[N]; void up(int pos, int val) { while (pos <= n) { bit[pos] = max(bit[pos], val); pos += pos & -pos; } } int get(int pos) { int ret = -2e9; while (pos) { ret = max(ret, bit[pos]); pos -= pos & -pos; } return ret; } } bit[2]; int main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen ("task.inp", "r")) { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); } if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } cin >> n; for(int i = 1; i <= n; i++) { int x, y; cin >> x >> y; v.emplace_back(x, y); bit[0].bit[i] = bit[1].bit[i] = -2e9; } sort(v.begin(), v.end()); for(int i = 1; i <= n; i++) tie(x[i], e[i]) = v[i - 1]; v.clear(); for(int i = 1; i <= n; i++) v.emplace_back(e[i], i); sort(v.begin(), v.end()); int res = 0; while (!v.empty()) { int i = v.back().second; v.pop_back(); if (bit[0].get(i) >= x[i] + e[i] || bit[1].get(n - i + 1) >= e[i] - x[i]) continue; res++; bit[0].up(i, x[i] + e[i]); bit[1].up(n - i + 1, e[i] - x[i]); } cout << res; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 46 ms | 3400 KB | Output is correct |
3 | Correct | 64 ms | 4692 KB | Output is correct |
4 | Correct | 147 ms | 11324 KB | Output is correct |
5 | Correct | 93 ms | 8356 KB | Output is correct |
6 | Correct | 183 ms | 12232 KB | Output is correct |
7 | Correct | 223 ms | 12292 KB | Output is correct |
8 | Correct | 157 ms | 12124 KB | Output is correct |
9 | Correct | 147 ms | 12132 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 0 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 0 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 340 KB | Output is correct |
22 | Correct | 1 ms | 340 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 340 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 46 ms | 3400 KB | Output is correct |
3 | Correct | 64 ms | 4692 KB | Output is correct |
4 | Correct | 147 ms | 11324 KB | Output is correct |
5 | Correct | 93 ms | 8356 KB | Output is correct |
6 | Correct | 183 ms | 12232 KB | Output is correct |
7 | Correct | 223 ms | 12292 KB | Output is correct |
8 | Correct | 157 ms | 12124 KB | Output is correct |
9 | Correct | 147 ms | 12132 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
15 | Correct | 0 ms | 340 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 340 KB | Output is correct |
21 | Correct | 0 ms | 340 KB | Output is correct |
22 | Correct | 0 ms | 340 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 0 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 1 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 129 ms | 9096 KB | Output is correct |
37 | Correct | 196 ms | 12580 KB | Output is correct |
38 | Correct | 193 ms | 12960 KB | Output is correct |
39 | Correct | 191 ms | 12484 KB | Output is correct |
40 | Correct | 194 ms | 12196 KB | Output is correct |
41 | Correct | 192 ms | 12932 KB | Output is correct |
42 | Correct | 219 ms | 12904 KB | Output is correct |
43 | Correct | 197 ms | 14156 KB | Output is correct |
44 | Correct | 173 ms | 14820 KB | Output is correct |
45 | Correct | 162 ms | 13956 KB | Output is correct |