oj.uz

Submission #373759

# Submission time Handle Problem Language Result Execution time Memory
373759 2021-03-05T16:20:04 Z sofapuden Wall (IOI14_wall) C++14
100 / 100
 1006 ms 216972 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6+5;
const int maxv = 1<<30;

struct seg{
	
	seg *r, *l;
	int lb, rb;
	bool ch;
	int mxval, mnval;
	int mid;

	seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
	

	void init(int lx, int rx){
		lb = lx, rb = rx;
		mid = (lx+rx)>>1;
	}

	void ex(){
		if(r == NULL){
			r = new seg;
			r->init(mid+1,rb);
		}
		if(l == NULL){
			l = new seg;
			l->init(lb,mid);
		}
	}
	void push(){
		r->mxval = min(r->mxval,mxval);
		r->mnval = min(r->mnval,r->mxval);
		r->mnval = max(r->mnval,mnval);
		r->mxval = max(r->mxval,r->mnval);
		r->ch = true;
		l->mxval = min(l->mxval,mxval);
		l->mnval = min(l->mnval,l->mxval);
		l->mnval = max(l->mnval,mnval);
		l->mxval = max(l->mxval,l->mnval);
		l->ch = true;
		mnval = 0;
		mxval = maxv;
		ch = false;
	}

	void add(int cl, int cr, int am){
		if(lb > cr || rb < cl)return;
		if(lb >= cl && rb <= cr){
			mnval = max(mnval,am);
			mxval = max(mxval,mnval);
			ch = true;
			return;
		}
		ex();
		if(ch)push();
		l->add(cl,cr,am);
		r->add(cl,cr,am);
	}
	void rem(int cl, int cr, int am){
		if(lb > cr || rb < cl)return;
		if(lb >= cl && rb <= cr){
			mxval = min(mxval,am);
			mnval = min(mnval,mxval);
			ch = true;
			return;
		}
		ex();
		if(ch)push();
		l->rem(cl,cr,am);
		r->rem(cl,cr,am);
	}
	int fin(int x){
		if(lb == rb){
			return mnval;
		}
		ex();
		if(ch)push();
		if(x > mid)return r->fin(x);
		return l->fin(x);
	}	
};

seg *root = new seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root->init(0,n-1);
	for(int i = 0; i < k; ++i){
		if(op[i] == 1){
			root->add(left[i],right[i],height[i]);
		}
		else{
			root->rem(left[i],right[i],height[i]);
		}
	}
	for(int i = 0; i < n; ++i){
		finalHeight[i] = root->fin(i);
	}
	return;
	
}

Compilation message

wall.cpp: In constructor 'seg::seg()':
wall.cpp:11:11: warning: 'seg::l' will be initialized after [-Wreorder]
   11 |  seg *r, *l;
      |           ^
wall.cpp:11:7: warning:   'seg* seg::r' [-Wreorder]
   11 |  seg *r, *l;
      |       ^
wall.cpp:17:2: warning:   when initialized here [-Wreorder]
   17 |  seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
      |  ^~~
wall.cpp:14:13: warning: 'seg::mnval' will be initialized after [-Wreorder]
   14 |  int mxval, mnval;
      |             ^~~~~
wall.cpp:14:6: warning:   'int seg::mxval' [-Wreorder]
   14 |  int mxval, mnval;
      |      ^~~~~
wall.cpp:17:2: warning:   when initialized here [-Wreorder]
   17 |  seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
      |  ^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 155 ms 8172 KB Output is correct
3 Correct 216 ms 5460 KB Output is correct
4 Correct 641 ms 18412 KB Output is correct
5 Correct 267 ms 18668 KB Output is correct
6 Correct 279 ms 18796 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 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 1516 KB Output is correct
5 Correct 6 ms 1516 KB Output is correct
6 Correct 6 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 159 ms 12268 KB Output is correct
9 Correct 194 ms 9216 KB Output is correct
10 Correct 707 ms 21672 KB Output is correct
11 Correct 277 ms 21740 KB Output is correct
12 Correct 263 ms 22252 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 12396 KB Output is correct
15 Correct 33 ms 3180 KB Output is correct
16 Correct 704 ms 21888 KB Output is correct
17 Correct 272 ms 21868 KB Output is correct
18 Correct 267 ms 21868 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 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 1516 KB Output is correct
5 Correct 6 ms 1516 KB Output is correct
6 Correct 6 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 157 ms 12396 KB Output is correct
9 Correct 189 ms 9196 KB Output is correct
10 Correct 674 ms 21484 KB Output is correct
11 Correct 269 ms 21740 KB Output is correct
12 Correct 281 ms 22280 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 162 ms 13036 KB Output is correct
15 Correct 33 ms 3180 KB Output is correct
16 Correct 665 ms 22308 KB Output is correct
17 Correct 270 ms 21868 KB Output is correct
18 Correct 264 ms 21740 KB Output is correct
19 Correct 1006 ms 216972 KB Output is correct
20 Correct 996 ms 214056 KB Output is correct
21 Correct 993 ms 216660 KB Output is correct
22 Correct 988 ms 214124 KB Output is correct
23 Correct 995 ms 214176 KB Output is correct
24 Correct 990 ms 214252 KB Output is correct
25 Correct 985 ms 214228 KB Output is correct
26 Correct 1006 ms 216684 KB Output is correct
27 Correct 998 ms 216812 KB Output is correct
28 Correct 991 ms 214180 KB Output is correct
29 Correct 987 ms 213996 KB Output is correct
30 Correct 987 ms 213996 KB Output is correct