# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
147264 |
2019-08-28T15:36:32 Z |
karma |
벽 (IOI14_wall) |
C++11 |
|
717 ms |
13640 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = int(2e6) + 7;
const int oo = int(1e9) + 7;
struct TSegment{
int n, low, high, val;
vector<int> st, l, h;
TSegment(int n = 0): n(n) {
st.resize(n << 2 | 1), l.resize(n << 2 | 1), h.resize(n << 2 | 1);
}
void Build(int x, int low, int high) {
l[x] = low, h[x] = high, st[x] = 0;
if(l[x] == h[x]) return;
int mid = (low + high) >> 1;
Build(x << 1, low, mid); Build(x << 1 | 1, mid + 1, high);
}
void Down(int x) {
if(l[x] == h[x] || st[x] == -oo) return;
if(1ll * st[x << 1] * st[x] < 0) st[x << 1] = st[x];
else st[x << 1] = max(st[x], st[x << 1]);
if(1ll * st[x << 1 | 1] * st[x] < 0) st[x << 1 | 1] = st[x];
else st[x << 1 | 1] = max(st[x], st[x << 1 | 1]);
st[x] = -oo;
}
void Update(int x) {
Down(x);
if(l[x] > high || h[x] < low) return;
if(l[x] >= low && h[x] <= high) {
if(l[x] != h[x]) st[x] = val;
else {
if(1ll * st[x] * val < 0) st[x] = val;
else st[x] = max(st[x], val);
}
Down(x);
return;
}
Update(x << 1); Update(x << 1 | 1);
}
void Update(int l, int h, int v) {
low = l, high = h, val = v;
Update(1);
}
int Query(int x, int pos) {
Down(x);
if(l[x] > pos || h[x] < pos) return -oo;
if(l[x] == pos && h[x] == pos) return st[x];
return max(Query(x << 1, pos), Query(x << 1 | 1, pos));
}
} Irene;
void buildWall(int n, int k, int op[], int lef[], int rig[], int h[], int ans[])
{
Irene = TSegment(n);
Irene.Build(1, 0, n - 1);
for(int i = 0; i < k; ++i) {
if(op[i] == 1) {
if(h[i]) Irene.Update(lef[i], rig[i], h[i]);
}else Irene.Update(lef[i], rig[i], -h[i] - 1);
}
for(int i = 0; i < n; ++i) {
ans[i] = Irene.Query(1, i);
if(ans[i] < 0) ans[i] = -ans[i] - 1;
}
}
//int _n, _k, _op[N], _lef[N], _rig[N], _h[N], ans[N];
//
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
// if(fopen("test.inp", "r")) {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// }
// cin >> _n >> _k;
// for(int i = 0; i < _k; ++i) cin >> _op[i] >> _lef[i] >> _rig[i] >> _h[i];
// buildWall(_n, _k, _op, _lef, _rig, _h, ans);
// for(int i = 0; i < _n; ++i) cout << ans[i] << ' ';
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
167 ms |
8152 KB |
Output is correct |
3 |
Correct |
276 ms |
4640 KB |
Output is correct |
4 |
Incorrect |
717 ms |
13640 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |