oj.uz

Submission #854549

# Submission time Handle Problem Language Result Execution time Memory
854549 2023-09-28T01:03:50 Z KN200711 Wall (IOI14_wall) C++14
100 / 100
 649 ms 79984 KB 
#include "wall.h"
# include <bits/stdc++.h>
using namespace std;

const int MXN = 2e6;
int bl[4 * MXN + 1], br[4 * MXN + 1];

void build(int lf, int rg, int nd) {
	bl[nd] = br[nd] = 0;
	if(lf != rg) {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd+1);
		build(mid+1, rg, 2*nd+2);
	}
}

void upd_lazy(int lf, int rg, int nd) {
	if(lf != rg) {
		int mid = (lf + rg) / 2;
		if(bl[2*nd+1] > bl[nd]) bl[2*nd+1] = bl[nd];
		else if(bl[2*nd+1] < br[nd]) bl[2*nd+1] = br[nd];
		
		if(bl[2*nd+2] > bl[nd]) bl[2*nd+2] = bl[nd];
		else if(bl[2*nd+2] < br[nd]) bl[2*nd+2] = br[nd];
		
		if(br[2*nd+1] > bl[nd]) br[2*nd+1] = bl[nd];
		else if(br[2*nd+1] < br[nd]) br[2*nd+1] = br[nd];
		
		if(br[2*nd+2] > bl[nd]) br[2*nd+2] = bl[nd];
		else if(br[2*nd+2] < br[nd]) br[2*nd+2] = br[nd];
	}
}

void upd(int lf, int rg, int nd, int clf, int crg, int op, int pos) {
	upd_lazy(lf, rg, nd);
	if(clf > rg || lf > crg) return;
	else if(clf <= lf && rg <= crg) {
		if(op == 1) {
		//	cout<<"upd : "<<lf<<" "<<rg<<" "<<nd<<" "<<bl[nd]<<" "<<pos<<endl;
			if(bl[nd] <= pos) bl[nd] = br[nd] = pos;
			else if(br[nd] <= pos) br[nd] = pos;
		} else {
			if(br[nd] >= pos) bl[nd] = br[nd] = pos;
			else if(bl[nd] >= pos) bl[nd] = pos;
		}
		upd_lazy(lf, rg, nd);
	} else {
		int mid = (lf + rg) / 2;
		upd(lf, mid, 2*nd+1, clf, crg, op, pos);
		upd(mid+1, rg, 2*nd+2, clf, crg, op, pos);
		bl[nd] = max(bl[2*nd+1], bl[2*nd+2]);
		br[nd] = min(br[2*nd+1], br[2*nd+2]);
	}
}

int val[MXN + 1];

void fn(int lf, int rg, int nd) {
	upd_lazy(lf, rg, nd);
	if(lf == rg) {
		val[lf] = bl[nd];
	} else {
		int mid = (lf + rg) / 2;
		fn(lf, mid, 2*nd+1);
		fn(mid+1, rg, 2*nd+2);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(0, n-1, 0);
	for(int i=0;i<k;i++) {
		upd(0, n-1, 0, left[i], right[i], op[i], height[i]);
	}
	fn(0, n-1, 0);
	for(int i=0;i<n;i++) finalHeight[i] = val[i];
}

Compilation message

wall.cpp: In function 'void upd_lazy(int, int, int)':
wall.cpp:19:7: warning: unused variable 'mid' [-Wunused-variable]
   19 |   int mid = (lf + rg) / 2;
      |       ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 6 ms 6744 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 5 ms 6744 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 102 ms 18112 KB Output is correct
3 Correct 151 ms 13580 KB Output is correct
4 Correct 429 ms 28900 KB Output is correct
5 Correct 258 ms 29708 KB Output is correct
6 Correct 259 ms 28240 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 7 ms 6800 KB Output is correct
5 Correct 6 ms 6748 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 110 ms 18064 KB Output is correct
9 Correct 152 ms 13652 KB Output is correct
10 Correct 426 ms 28716 KB Output is correct
11 Correct 255 ms 29732 KB Output is correct
12 Correct 257 ms 28504 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 115 ms 18188 KB Output is correct
15 Correct 32 ms 7656 KB Output is correct
16 Correct 564 ms 29076 KB Output is correct
17 Correct 269 ms 28496 KB Output is correct
18 Correct 266 ms 28496 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4452 KB Output is correct
2 Correct 2 ms 4672 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 6 ms 6788 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 5 ms 6748 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 101 ms 18176 KB Output is correct
9 Correct 151 ms 13652 KB Output is correct
10 Correct 430 ms 28836 KB Output is correct
11 Correct 258 ms 29776 KB Output is correct
12 Correct 261 ms 28408 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 111 ms 18192 KB Output is correct
15 Correct 33 ms 7764 KB Output is correct
16 Correct 569 ms 29180 KB Output is correct
17 Correct 270 ms 28344 KB Output is correct
18 Correct 271 ms 28588 KB Output is correct
19 Correct 642 ms 79944 KB Output is correct
20 Correct 641 ms 77472 KB Output is correct
21 Correct 646 ms 79984 KB Output is correct
22 Correct 649 ms 77420 KB Output is correct
23 Correct 644 ms 77680 KB Output is correct
24 Correct 645 ms 77652 KB Output is correct
25 Correct 639 ms 77768 KB Output is correct
26 Correct 643 ms 79940 KB Output is correct
27 Correct 643 ms 79916 KB Output is correct
28 Correct 645 ms 77460 KB Output is correct
29 Correct 636 ms 77580 KB Output is correct
30 Correct 634 ms 77392 KB Output is correct