oj.uz

Submission #153843

# Submission time Handle Problem Language Result Execution time Memory
153843 2019-09-17T01:52:54 Z dennisstar Wall (IOI14_wall) C++11
100 / 100
 1327 ms 77464 KB 
#include "wall.h"
#include <utility>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX=(1<<21);

int ans[(1<<21)];

struct seg{
	pii pi[(1<<22)];
	void lazy(int val, int ind, int op) {
		if (op==1) {
			pi[ind].fi=max(val, pi[ind].first);
			pi[ind].se=max(val, pi[ind].second);
		}
		if (op==2) {
			pi[ind].fi=min(val, pi[ind].first);
			pi[ind].se=min(val, pi[ind].second);
		}
	}
	void update(int s, int e, int i, int ds, int de, int h, int op) {
		if (!(s<=de&&ds<=e)) return ;
		if (s<=ds&&de<=e) {
			lazy(h, i, op);
			if (s==e) ans[s]=pi[i].fi;
		}
		else {
			lazy(pi[i].fi, i*2, 1); lazy(pi[i].se, i*2, 2);
			lazy(pi[i].fi, i*2+1, 1); lazy(pi[i].se, i*2+1, 2);
			pi[i]={0,(1<<30)};
			int md=(ds+de)/2;
			update(s, e, i*2, ds, md, h, op);
			update(s, e, i*2+1, md+1, de, h, op);
		}
	}
}T;


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i=0; i<k; i++) T.update(left[i], right[i], 1, 0, n-1, height[i], op[i]);
	for (int i=0; i<n; i++) T.update(i, i, 1, 0, n-1, 0, 1);
	for (int i=0; i<n; i++) finalHeight[i]=ans[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 9 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 179 ms 13956 KB Output is correct
3 Correct 202 ms 8000 KB Output is correct
4 Correct 589 ms 20832 KB Output is correct
5 Correct 359 ms 21832 KB Output is correct
6 Correct 353 ms 20344 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 187 ms 13916 KB Output is correct
9 Correct 202 ms 8068 KB Output is correct
10 Correct 606 ms 20852 KB Output is correct
11 Correct 353 ms 21880 KB Output is correct
12 Correct 342 ms 20360 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 181 ms 14088 KB Output is correct
15 Correct 37 ms 2168 KB Output is correct
16 Correct 585 ms 21212 KB Output is correct
17 Correct 349 ms 20632 KB Output is correct
18 Correct 344 ms 20632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 10 ms 932 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 179 ms 14024 KB Output is correct
9 Correct 200 ms 8056 KB Output is correct
10 Correct 583 ms 20856 KB Output is correct
11 Correct 360 ms 22288 KB Output is correct
12 Correct 342 ms 20344 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 181 ms 14072 KB Output is correct
15 Correct 36 ms 2040 KB Output is correct
16 Correct 594 ms 21112 KB Output is correct
17 Correct 347 ms 20552 KB Output is correct
18 Correct 343 ms 20560 KB Output is correct
19 Correct 1312 ms 77440 KB Output is correct
20 Correct 1319 ms 74940 KB Output is correct
21 Correct 1304 ms 77464 KB Output is correct
22 Correct 1298 ms 74920 KB Output is correct
23 Correct 1298 ms 74860 KB Output is correct
24 Correct 1297 ms 74952 KB Output is correct
25 Correct 1305 ms 74760 KB Output is correct
26 Correct 1299 ms 77360 KB Output is correct
27 Correct 1307 ms 77344 KB Output is correct
28 Correct 1327 ms 74892 KB Output is correct
29 Correct 1322 ms 74928 KB Output is correct
30 Correct 1325 ms 74956 KB Output is correct