oj.uz

Submission #355567

# Submission time Handle Problem Language Result Execution time Memory
355567 2021-01-22T17:35:16 Z Mefarnis Wall (IOI14_wall) C++14
100 / 100
 1424 ms 110316 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
#define maxn 2000001
using namespace std;
typedef pair<int,int> pi;

int n,k;
int ids[maxn];
pi tree[4*maxn];
pi lazy[4*maxn];

void init(int x , int y , int id) {
	tree[id] = pi(0,0);
	lazy[id] = pi(-1,-1);
	if(x == y) {
		ids[x] = id;
		return;
	}
	int mid = (x+y) >> 1;
	init(x,mid,2*id);
	init(mid+1,y,2*id+1);
}

void pushLazy(pi& s , pi& t , int id , bool further) {
	if(s.fi != -1 && s.se != -1) {
		if(t.fi == -1 && t.se == -1)
			t = s;
		else if(t.fi != -1 && t.se == -1) {
			if(t.fi <= s.se)
				t = pi(s.se,s.se);
			else if(t.fi >= s.fi)
				t = s;
			else
				t.se = s.se;
		}
		else if(t.fi == -1 && t.se != -1) {
			if(t.se >= s.fi)
				t = pi(s.fi,s.fi);
			else if(t.se <= s.se)
				t = s;
			else
				t.fi = s.fi;
		}
		else {
			if(t.fi <= s.se)
				t = pi(s.se,s.se);
			else if(t.se >= s.fi)
				t = pi(s.fi,s.fi);
			else {
				t.se = max(t.se,s.se);
				t.fi = min(t.fi,s.fi);
			}
		}
	}
	else if(s.fi != -1) {
		if(t.fi == -1 && t.se == -1)
			t.fi = s.fi;
		else if(t.fi != -1 && t.se == -1)
			t.fi = min(t.fi,s.fi);
		else if(t.fi == -1 && t.se != -1) {
			if(s.fi <= t.se)
				t = pi(s.fi,s.fi);
			else
				t.fi = s.fi;
		}
		else {
			if(s.fi <= t.se)
				t = pi(s.fi,s.fi);
			else
				t.fi = min(t.fi,s.fi); 
		}
	}
	else if(s.se != -1) {
		if(t.fi == -1 && t.se == -1)
			t.se = s.se;
		else if(t.fi == -1 && t.se != -1)
			t.se = max(t.se,s.se);
		else if(t.fi != -1 && t.se == -1) {
			if(s.se >= t.fi)
				t = pi(s.se,s.se);
			else
				t.se = s.se;
		}
		else {
			if(s.se >= t.fi)
				t = pi(s.se,s.se);
			else
				t.se = max(t.se,s.se);
		}
	}
	if(further) {
		pushLazy(lazy[id],lazy[2*id],2*id,false);
		pushLazy(lazy[id],lazy[2*id+1],2*id+1,false);
	}
}

void updateMin(int cx , int cy , int qx , int qy , int val , int id) {
	pushLazy(lazy[id],tree[id],id,cx!=cy);
	lazy[id] = pi(-1,-1);
	if(qy < cx || cy < qx)
		return;
	if(qx <= cx && cy <= qy) {
		lazy[id].fi = val;
		pushLazy(lazy[id],tree[id],id,cx!=cy);
		lazy[id] = pi(-1,-1);
		return;
	}
	int mid = (cx + cy) >> 1;
	updateMin(cx,mid,qx,qy,val,2*id);
	updateMin(mid+1,cy,qx,qy,val,2*id+1);
	tree[id].fi = min(tree[2*id].fi,tree[2*id+1].fi);
	tree[id].se = max(tree[2*id].se,tree[2*id+1].se);
}

void updateMax(int cx , int cy , int qx , int qy , int val , int id) {
	pushLazy(lazy[id],tree[id],id,cx!=cy);
	lazy[id] = pi(-1,-1);
	if(qy < cx || cy < qx)
		return;
	if(qx <= cx && cy <= qy) {
		lazy[id].se = val;
		pushLazy(lazy[id],tree[id],id,cx!=cy);
		lazy[id] = pi(-1,-1);
		return;
	}
	int mid = (cx + cy) >> 1;
	updateMax(cx,mid,qx,qy,val,2*id);
	updateMax(mid+1,cy,qx,qy,val,2*id+1);
	tree[id].fi = min(tree[2*id].fi,tree[2*id+1].fi);
	tree[id].se = max(tree[2*id].se,tree[2*id+1].se);
}

void query(int x , int y , int id) {
	pushLazy(lazy[id],tree[id],id,x!=y);
	lazy[id] = pi(-1,-1);
	if(x == y)
		return;
	int mid = (x+y) >> 1;
	query(x,mid,2*id);
	query(mid+1,y,2*id+1);
}

void buildWall(int N, int K, int op[], int l[], int r[], int h[], int ans[]) {
	n = N , k = K;
	init(0,n-1,1);
	for( int i = 0 ; i < k ; i++ ) {
		if(op[i] == 1)
			updateMax(0,n-1,l[i],r[i],h[i],1);
		else
			updateMin(0,n-1,l[i],r[i],h[i],1);
	}
	query(0,n-1,1);
	for( int i = 0 ; i < n ; i++ )
		ans[i] = tree[ids[i]].se;
}

/*
int main() {
	int n = 10 , k = 6;
	int op[6] = {1,2,2,1,1,2};
	int l[6] = {1,4,3,0,2,6};
	int r[6] = {8,9,6,5,2,7};
	int h[6] = {4,1,5,3,5,0};
	int ans[n];
	buildWall(n, 6, op, l, r, h, ans);
	for( int i = 0 ; i < n ; i++ )
		printf("%d ",ans[i]);
	puts("");
	return 0;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 12 ms 1132 KB Output is correct
5 Correct 8 ms 1132 KB Output is correct
6 Correct 8 ms 1132 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 168 ms 14060 KB Output is correct
3 Correct 371 ms 8620 KB Output is correct
4 Correct 1148 ms 22884 KB Output is correct
5 Correct 501 ms 24044 KB Output is correct
6 Correct 527 ms 22412 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 12 ms 1132 KB Output is correct
5 Correct 8 ms 1132 KB Output is correct
6 Correct 10 ms 1280 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 161 ms 14060 KB Output is correct
9 Correct 356 ms 8684 KB Output is correct
10 Correct 1161 ms 22900 KB Output is correct
11 Correct 493 ms 24044 KB Output is correct
12 Correct 493 ms 22364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 165 ms 14060 KB Output is correct
15 Correct 68 ms 2668 KB Output is correct
16 Correct 1363 ms 23148 KB Output is correct
17 Correct 497 ms 22636 KB Output is correct
18 Correct 518 ms 22564 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 12 ms 1132 KB Output is correct
5 Correct 9 ms 1132 KB Output is correct
6 Correct 9 ms 1132 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 176 ms 14060 KB Output is correct
9 Correct 361 ms 8604 KB Output is correct
10 Correct 1288 ms 22892 KB Output is correct
11 Correct 496 ms 23916 KB Output is correct
12 Correct 485 ms 22380 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 182 ms 14060 KB Output is correct
15 Correct 68 ms 2668 KB Output is correct
16 Correct 1372 ms 23140 KB Output is correct
17 Correct 497 ms 22636 KB Output is correct
18 Correct 491 ms 22636 KB Output is correct
19 Correct 1331 ms 110232 KB Output is correct
20 Correct 1275 ms 107800 KB Output is correct
21 Correct 1297 ms 110192 KB Output is correct
22 Correct 1315 ms 107756 KB Output is correct
23 Correct 1292 ms 107884 KB Output is correct
24 Correct 1307 ms 107800 KB Output is correct
25 Correct 1288 ms 107672 KB Output is correct
26 Correct 1424 ms 110288 KB Output is correct
27 Correct 1294 ms 110316 KB Output is correct
28 Correct 1291 ms 107688 KB Output is correct
29 Correct 1294 ms 107816 KB Output is correct
30 Correct 1306 ms 107800 KB Output is correct