oj.uz

Submission #784579

# Submission time Handle Problem Language Result Execution time Memory
784579 2023-07-16T10:12:15 Z FatihSolak Wall (IOI14_wall) C++17
0 / 100
 229 ms 13884 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct SegTree{
	struct node{
		int mini1,mini2;
		int maxi1,maxi2;
		node():mini1(0),mini2(INF),maxi1(0),maxi2(-INF){}
		void setmax(int x){
			if(x <= mini1)
				return;
			if(maxi1 == mini1)
				maxi1 = x;
			if(maxi2 == mini1)
				maxi2 = x;
			mini1 = x;
		}
		void setmin(int x){
			if(x >= maxi1)
				return;
			if(mini1 == maxi1)
				mini1 = x;
			if(mini2 == maxi1)
				mini2 = x;
			maxi1 = x;
		}		
	};
	node merge(node a,node b){
		if(a.maxi1 < b.maxi1){
			a.maxi2 = a.maxi1;
			a.maxi1 = b.maxi1;
		}
		if(a.maxi1 == b.maxi1){
			a.maxi2 = max(a.maxi2,b.maxi2);
		}
		else{
			a.maxi2 = max(a.maxi2,b.maxi1);
		}
		if(a.mini1 > b.mini1){
			a.mini2 = a.mini1;
			a.mini1 = b.mini1;
		}
		if(a.mini1 == b.mini1){
			a.mini2 = min(a.mini2,b.mini2);
		}
		else{
			a.mini2 = min(a.mini2,b.mini1);
		}
		return a;
	}
	vector<node> t;
	int n;
	SegTree(int sz){
		n = sz;
		t.assign(4*n,node());
	}
	void push(int v){
		t[v*2].setmax(t[v].maxi1);
		t[v*2].setmin(t[v].mini1);
		t[v*2 + 1].setmax(t[v].maxi1);
		t[v*2 + 1].setmin(t[v].mini1);
	}
	void upd(int v,int tl,int tr,int l,int r,int val,int op){
		if(tr < l || r < tl || (op == 1 && t[v].mini1 >= val) || (op == 2 && t[v].maxi1 <= val)){
			return;
		}
		if(l <= tl && tr <= r && ((op == 1 && t[v].mini2 > val) || (op == 2 && t[v].maxi2 < val))){
			if(op == 1){
				t[v].setmax(val);
			}
			else t[v].setmin(val);
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val,op);
		upd(v*2 + 1,tm+1,tr,l,r,val,op);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int pos){
		if(tl == tr){
			return t[v].maxi1;
		}
		push(v);
		int tm = (tl + tr)/2;
		if(pos <= tm){
			return get(v*2,tl,tm,pos);
		}
		return get(v*2+1,tm+1,tr,pos);
	}
	void upd(int l,int r,int val,int op){
		upd(1,0,n-1,l,r,val,op);
	}
	int get(int pos){
		return get(1,0,n-1,pos);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree t(n);
	for(int i = 0;i<k;i++){
		t.upd(left[i],right[i],height[i],op[i]);
	}
	for(int i = 0;i<n;i++){
		finalHeight[i] = t.get(i);
	}
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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