oj.uz

Submission #52101

# Submission time Handle Problem Language Result Execution time Memory
52101 2018-06-23T23:01:18 Z spencercompton Wall (IOI14_wall) C++17
100 / 100
 1681 ms 393216 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int inf = 100000;
int low[4194304];
int high[4194304];
int l[4194304];
int r[4194304];
int point = 0;
int create(int s, int e){
	int now = point++;
	if(s==e){
		l[now] = -1;
		r[now] = -1;
		low[now] = 0;
		high[now] = 0;
	}
	else{
		int lv = create(s,(s+e)/2);
		l[now] = lv;
		int rv = create((s+e)/2+1,e);
		r[now] = rv;
		low[now] = 0;
		high[now] = 100000;
	}
	return now;
}
void push(int now, int nlow, int nhigh){
	if(nlow>=high[now]){
		high[now] = nlow;
		low[now] = nlow;
	}
	else if(nhigh<=low[now]){
		low[now] = nhigh;
		high[now] = nhigh;
	}
	else{
		high[now] = min(high[now],nhigh);
		low[now] = max(low[now],nlow);
	}
}
void upd(int now, int st, int en, int s, int e, int nlow, int nhigh){
	if(s==e){
		push(now,nlow,nhigh);
		return;
	}
	if(st<=s && e<=en){
		push(now,nlow,nhigh);
		return;
	}
	push(l[now],low[now],high[now]);
	push(r[now],low[now],high[now]);
	low[now] = 0;
	high[now] = inf;
	if(st<=(s+e)/2){
		upd(l[now],st,en,s,(s+e)/2,nlow,nhigh);
	}
	if(en>(s+e)/2){
		upd(r[now],st,en,(s+e)/2+1,e,nlow,nhigh);
	}
}
int get(int ind, int now, int s, int e){
	if(s==e){
		// cout << "@ " << s << " " << e << " " << low[now] << " " << high[now] << endl;
		assert(low[now]==high[now]);
		return low[now];
	}
	push(l[now],low[now],high[now]);
	push(r[now],low[now],high[now]);
	low[now] = 0;
	high[now] = inf;
	if(ind<=(s+e)/2){
		return get(ind,l[now],s,(s+e)/2);
	}
	else{
		return get(ind,r[now],(s+e)/2+1,e);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	// cout << "A " << endl;
	int t = create(0,n-1);
	// cout << "B " << endl;
	for(int i = 0; i<k; i++){
		// cout << "C " << i << " " << k << endl;
		if(op[i]==1){
			//add
			// cout << "!  " << t << " " << left[i] << " " << right[i] << " " << height[i] << endl;
			upd(t,left[i],right[i],0,n-1,height[i],inf);
		}
		else{
			//remove
			upd(t,left[i],right[i],0,n-1,0,height[i]);
		}
	}
	// cout << "D " << endl;
	for(int i = 0; i<n; i++){
		finalHeight[i] = get(i,t,0,n-1);
		// cout << "E " << i << " " << finalHeight[i] << endl;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 496 KB Output is correct
3 Correct 4 ms 644 KB Output is correct
4 Correct 11 ms 1248 KB Output is correct
5 Correct 9 ms 1332 KB Output is correct
6 Correct 10 ms 1552 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1552 KB Output is correct
2 Correct 193 ms 14604 KB Output is correct
3 Correct 213 ms 14704 KB Output is correct
4 Correct 665 ms 32044 KB Output is correct
5 Correct 466 ms 42580 KB Output is correct
6 Correct 374 ms 51268 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 51268 KB Output is correct
2 Correct 4 ms 51268 KB Output is correct
3 Correct 4 ms 51268 KB Output is correct
4 Correct 11 ms 51268 KB Output is correct
5 Correct 9 ms 51268 KB Output is correct
6 Correct 10 ms 51268 KB Output is correct
7 Correct 2 ms 51268 KB Output is correct
8 Correct 200 ms 53244 KB Output is correct
9 Correct 281 ms 53244 KB Output is correct
10 Correct 817 ms 70304 KB Output is correct
11 Correct 411 ms 81036 KB Output is correct
12 Correct 374 ms 89684 KB Output is correct
13 Correct 2 ms 89684 KB Output is correct
14 Correct 203 ms 91124 KB Output is correct
15 Correct 47 ms 91124 KB Output is correct
16 Correct 849 ms 105352 KB Output is correct
17 Correct 441 ms 114476 KB Output is correct
18 Correct 633 ms 123452 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 123452 KB Output is correct
2 Correct 4 ms 123452 KB Output is correct
3 Correct 5 ms 123452 KB Output is correct
4 Correct 11 ms 123452 KB Output is correct
5 Correct 9 ms 123452 KB Output is correct
6 Correct 9 ms 123452 KB Output is correct
7 Correct 2 ms 123452 KB Output is correct
8 Correct 175 ms 125712 KB Output is correct
9 Correct 210 ms 125712 KB Output is correct
10 Correct 631 ms 142748 KB Output is correct
11 Correct 398 ms 153484 KB Output is correct
12 Correct 371 ms 162092 KB Output is correct
13 Correct 3 ms 162092 KB Output is correct
14 Correct 181 ms 163696 KB Output is correct
15 Correct 46 ms 163696 KB Output is correct
16 Correct 826 ms 177940 KB Output is correct
17 Correct 387 ms 186920 KB Output is correct
18 Correct 428 ms 195888 KB Output is correct
19 Correct 1480 ms 283000 KB Output is correct
20 Correct 1448 ms 291064 KB Output is correct
21 Correct 1558 ms 303880 KB Output is correct
22 Correct 1681 ms 311988 KB Output is correct
23 Correct 1493 ms 322444 KB Output is correct
24 Correct 1491 ms 332808 KB Output is correct
25 Correct 1506 ms 343200 KB Output is correct
26 Correct 1543 ms 356140 KB Output is correct
27 Correct 1543 ms 366640 KB Output is correct
28 Correct 1459 ms 374728 KB Output is correct
29 Correct 1444 ms 385100 KB Output is correct
30 Correct 1496 ms 393216 KB Output is correct