oj.uz

답안 #726813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
726813 2023-04-19T11:50:07 Z allin27x 벽 (IOI14_wall) C++17
61 / 100
 976 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long int;
struct SGT{
	vector<vector<int>> t;
	int n;
	int ofs;
	SGT(int sz){
		n= sz;
		ofs = 1ll<<(int)(ceil(log2(n+1)));
		t.resize(4*n, {0, (int)2e9});
	}

	void apply(int p){
		if (t[p][0]>t[2*p][1]) t[2*p][0]=t[p][0],t[2*p][1]=t[p][0]; else
		if (t[2*p][0]>t[p][1]) t[2*p][0]=t[p][1], t[2*p][1]=t[p][1]; else
		t[2*p][0]=max(t[2*p][0],t[p][0]), t[2*p][1]=min(t[2*p][1], t[p][1]);

		if (t[p][0]>t[2*p+1][1]) t[2*p+1][0]=t[p][0],t[2*p+1][1]=t[p][0]; else
		if (t[2*p+1][0]>t[p][1]) t[2*p+1][0]=t[p][1], t[2*p+1][1]=t[p][1]; else
		t[2*p+1][0]=max(t[2*p+1][0],t[p][0]), t[2*p+1][1]=min(t[2*p+1][1], t[p][1]);

		t[p][0] = 0; t[p][1] = (int)2e9;
	}

	void update(int p, int tl, int tr, int l ,int r, int h, int o){

		if (p<ofs) apply(p);
		if (l>r) return;
		if (tl==l && tr==r){
            if (o==0){
                t[p][0] = max(t[p][0], h); t[p][1] = max(t[p][1], t[p][0]);
            } else {
                t[p][1] = min(t[p][1], h); t[p][0] = min(t[p][0], t[p][1]);
            }
			return;
		}
		int tm = (tl+tr)>>1;
		update(2*p, tl, tm, l, min(tm, r), h, o);
		update(2*p+1, tm+1, tr, max(l,tm+1), r, h, o);
	}

	void update(int l, int r, int h, int o){

		update(1, 0, ofs-1, l, r, h, o);
	}

	void push(){
		for (int i=1; i<ofs; i++){
			apply(i);
		}
	}
};


void buildWall(int n, int k, int op[], int l[],int r[],int h[], int ans[]){
	SGT st(n);
	for (int i=0; i<k; i++){
		st.update(l[i], r[i], h[i], op[i]-1);
	}
	st.push();
	for (int i=0; i<n; i++) ans[i] = min(st.t[i+st.ofs][0], st.t[i+st.ofs][1]);
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 2612 KB Output is correct
5 Correct 8 ms 2612 KB Output is correct
6 Correct 7 ms 2608 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 126 ms 8320 KB Output is correct
3 Correct 203 ms 7860 KB Output is correct
4 Correct 755 ms 30688 KB Output is correct
5 Correct 349 ms 30692 KB Output is correct
6 Correct 330 ms 30608 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 124 ms 8368 KB Output is correct
9 Correct 207 ms 7844 KB Output is correct
10 Correct 781 ms 30796 KB Output is correct
11 Correct 339 ms 30740 KB Output is correct
12 Correct 325 ms 30688 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 131 ms 8352 KB Output is correct
15 Correct 47 ms 4820 KB Output is correct
16 Correct 969 ms 30636 KB Output is correct
17 Correct 337 ms 30800 KB Output is correct
18 Correct 339 ms 30688 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 10 ms 2676 KB Output is correct
5 Correct 8 ms 2672 KB Output is correct
6 Correct 8 ms 2644 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 123 ms 8268 KB Output is correct
9 Correct 219 ms 7876 KB Output is correct
10 Correct 943 ms 30632 KB Output is correct
11 Correct 337 ms 30636 KB Output is correct
12 Correct 332 ms 30604 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 125 ms 8280 KB Output is correct
15 Correct 49 ms 4820 KB Output is correct
16 Correct 976 ms 30812 KB Output is correct
17 Correct 366 ms 30692 KB Output is correct
18 Correct 336 ms 30716 KB Output is correct
19 Runtime error 374 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -