| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1079384 |
2024-08-28T13:45:47 Z |
vjudge1 |
벽 (IOI14_wall) |
C++17 |
|
578 ms |
110420 KB |
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5, inf = 1e9 + 5;
int mi[maxn << 2], mx[maxn << 2], N, res[maxn];
pair<int, int> lazy[maxn << 2];
void pull_inc(int id, int k) {
mi[id] = max(mi[id], k);
mx[id] = max(mx[id], k);
lazy[id].first = max(lazy[id].first, k);
lazy[id].second = max(lazy[id].second, k);
}
void pull_dec(int id, int k) {
mi[id] = min(mi[id], k);
mx[id] = min(mx[id], k);
lazy[id].first = min(lazy[id].first, k);
lazy[id].second = min(lazy[id].second, k);
}
void shift(int id){
if(lazy[id].first != -inf){
pull_inc(id << 1, lazy[id].first);
pull_inc(id << 1 | 1, lazy[id].first);
}
if(lazy[id].second != inf){
pull_dec(id << 1, lazy[id].second);
pull_dec(id << 1 | 1, lazy[id].second);
}
lazy[id] = {-inf, inf};
}
void upd(int L, int R, int k, int t, int id = 1, int tl = 0, int tr = N - 1) {
if (L > tr || R < tl) return;
if (L <= tl && R >= tr) {
if (t == 1) pull_inc(id, k);
else pull_dec(id, k);
return;
}
shift(id);
upd(L, R, k, t, id << 1, tl, (tl + tr) >> 1);
upd(L, R, k, t, id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
void get(int id = 1, int tl = 0, int tr = N - 1) {
if (tl == tr) { res[tl] = mi[id]; return; }
shift(id);
get(id << 1, tl, (tl + tr) >> 1);
get(id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
N = n;
for (int i = 0; i < k; i++) upd(left[i], right[i], height[i], op[i]);
get();
for (int i = 0; i < N; i++) finalHeight[i] = res[i];
return;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
80 ms |
13932 KB |
Output is correct |
| 3 |
Correct |
138 ms |
8532 KB |
Output is correct |
| 4 |
Correct |
400 ms |
22868 KB |
Output is correct |
| 5 |
Correct |
210 ms |
23892 KB |
Output is correct |
| 6 |
Correct |
202 ms |
22352 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
84 ms |
14116 KB |
Output is correct |
| 9 |
Correct |
135 ms |
8528 KB |
Output is correct |
| 10 |
Correct |
398 ms |
22804 KB |
Output is correct |
| 11 |
Correct |
206 ms |
23916 KB |
Output is correct |
| 12 |
Correct |
206 ms |
22488 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
85 ms |
13908 KB |
Output is correct |
| 15 |
Correct |
24 ms |
2640 KB |
Output is correct |
| 16 |
Correct |
502 ms |
23120 KB |
Output is correct |
| 17 |
Correct |
206 ms |
22464 KB |
Output is correct |
| 18 |
Correct |
211 ms |
22612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1156 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
86 ms |
14032 KB |
Output is correct |
| 9 |
Correct |
139 ms |
8532 KB |
Output is correct |
| 10 |
Correct |
391 ms |
23008 KB |
Output is correct |
| 11 |
Correct |
205 ms |
23964 KB |
Output is correct |
| 12 |
Correct |
207 ms |
22476 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
105 ms |
13908 KB |
Output is correct |
| 15 |
Correct |
25 ms |
2644 KB |
Output is correct |
| 16 |
Correct |
483 ms |
23048 KB |
Output is correct |
| 17 |
Correct |
220 ms |
22540 KB |
Output is correct |
| 18 |
Correct |
210 ms |
22608 KB |
Output is correct |
| 19 |
Correct |
516 ms |
110328 KB |
Output is correct |
| 20 |
Correct |
510 ms |
108036 KB |
Output is correct |
| 21 |
Correct |
509 ms |
110420 KB |
Output is correct |
| 22 |
Correct |
505 ms |
108036 KB |
Output is correct |
| 23 |
Correct |
502 ms |
107840 KB |
Output is correct |
| 24 |
Correct |
502 ms |
107860 KB |
Output is correct |
| 25 |
Correct |
519 ms |
107856 KB |
Output is correct |
| 26 |
Correct |
506 ms |
110164 KB |
Output is correct |
| 27 |
Correct |
512 ms |
110164 KB |
Output is correct |
| 28 |
Correct |
576 ms |
107600 KB |
Output is correct |
| 29 |
Correct |
578 ms |
107700 KB |
Output is correct |
| 30 |
Correct |
573 ms |
107740 KB |
Output is correct |
