Submission #1088363

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088363	2024-09-14T09:58:36 Z	Sunbae	Wall (IOI14_wall)	C++17	8 / 100	3000 ms	235960 KB

wall

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 2e6 + 1;
vector<tuple<int,int,int>> s[N<<2];
int L, R, v, ti, o, idx[N], A[N];
tuple<int,int,int> T[N];
void ini(int I, int lo, int hi){
	if(lo == hi){ idx[lo] = I; return;}
	int m = lo + ((hi-lo)>>1);
	ini(I<<1, lo, m); ini(I<<1|1, m+1, hi);
}
void upd(int I, int lo, int hi){
	if(lo > R || hi < L) return;
	if(L <= lo && hi <= R){ s[I].emplace_back(ti, o, v); return;}
	int m = lo + ((hi-lo)>>1);
	upd(I<<1, lo, m); upd(I<<1|1, m+1, hi);
}

void buildWall(int n, int k, int op[], int l[], int r[], int H[], int fH[]){
	for(int i = 0; i<(n<<2); ++i) s[i].clear();
	ini(1, 0, n-1);
	for(ti = 0; ti<k; ++ti){
		L = l[ti]; R = r[ti]; o = op[ti]-1; v = H[ti]; 
		upd(1, 0, n-1);  
	}
	for(int i = 0; i<n; ++i){
		int m = 0;
		for(int I = idx[i]; I; I>>=1) for(auto it : s[I]) T[m++] = it;
		sort(T, T+m);
		fH[i] = 0;
		for(int j = 0; j<m; ++j){
			auto it = T[j];
			o = get<1>(it); v = get<2>(it);
			fH[i] = !o ? max(fH[i], v) : min(fH[i], v);
		}
	}
}	

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	188240 KB	Output is correct
2	Correct	76 ms	188412 KB	Output is correct
3	Correct	81 ms	188496 KB	Output is correct
4	Correct	525 ms	189640 KB	Output is correct
5	Correct	527 ms	189264 KB	Output is correct
6	Correct	509 ms	189264 KB	Output is correct

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	188244 KB	Output is correct
2	Correct	173 ms	213696 KB	Output is correct
3	Execution timed out	3051 ms	235948 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	188244 KB	Output is correct
2	Correct	83 ms	188604 KB	Output is correct
3	Correct	74 ms	188504 KB	Output is correct
4	Correct	528 ms	189520 KB	Output is correct
5	Correct	534 ms	189260 KB	Output is correct
6	Correct	520 ms	189524 KB	Output is correct
7	Correct	76 ms	188244 KB	Output is correct
8	Correct	175 ms	213720 KB	Output is correct
9	Execution timed out	3088 ms	235952 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	188240 KB	Output is correct
2	Correct	80 ms	188496 KB	Output is correct
3	Correct	88 ms	188520 KB	Output is correct
4	Correct	535 ms	189520 KB	Output is correct
5	Correct	537 ms	189180 KB	Output is correct
6	Correct	501 ms	189392 KB	Output is correct
7	Correct	76 ms	188112 KB	Output is correct
8	Correct	177 ms	213600 KB	Output is correct
9	Execution timed out	3079 ms	235960 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-