oj.uz

Submission #726799

# Submission time Handle Problem Language Result Execution time Memory
726799 2023-04-19T11:30:49 Z allin27x Wall (IOI14_wall) C++17
0 / 100
 149 ms 8064 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){
			t[p][o] = h;
			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, (1ll<<(int)(ceil(log2(n+1))))-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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 149 ms 8064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -