oj.uz

Submission #170337

# Submission time Handle Problem Language Result Execution time Memory
170337 2019-12-24T20:12:59 Z ngmh Wall (IOI14_wall) C++11
100 / 100
 1556 ms 224764 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

struct node {
	int s, e, m, mini, maxi;
	node *l, *r;
	node(int _s, int _e){
		s = _s; e = _e; m = (s+e)/2; mini = 0; maxi = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void minimise(int v){
		maxi = min(v, max(mini, maxi));
		mini = min(mini, maxi);
	}
	void maximise(int v){
		mini = max(v, min(mini, maxi));
		maxi = max(mini, maxi);
	}
	void propogate(){
		if(s == e) return;
		l->maximise(mini);
		r->maximise(mini);
		l->minimise(maxi);
		r->minimise(maxi);
	}
	void backpropogate(){
		if(s == e) return;
		mini = min(l->mini, r->mini);
		maxi = max(l->maxi, r->maxi);
	}
	void add(int x, int y, int v){
		if(s == x && e == y){ maximise(v); return; }
		propogate();
		if(x > m) r->add(x, y, v);
		else if(y <= m) l->add(x, y, v);
		else l->add(x, m, v), r->add(m+1, y, v);
		backpropogate();
	}
	void remove(int x, int y, int v){
		if(s == x && e == y){ minimise(v); return; }
		propogate();
		if(x > m) r->remove(x, y, v);
		else if(y <= m) l->remove(x, y, v);
		else l->remove(x, m, v), r->remove(m+1, y, v);
		backpropogate();
	}
	int point_query(int x){
		if(s == e) return mini;
		propogate();
		if(x > m) return r->point_query(x);
		else if(x <= m) return l->point_query(x);
	}
} *root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root = new node(0, n-1);
	for(int i = 0; i < k; i++){
		if(op[i] == 1) root->add(left[i], right[i], height[i]);
		else root->remove(left[i], right[i], height[i]);
	}
	for(int i = 0; i < n; i++) finalHeight[i] = root->point_query(i);
}

Compilation message

wall.cpp: In member function 'int node::point_query(int)':
wall.cpp:56:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 6 ms 420 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 10 ms 1528 KB Output is correct
5 Correct 10 ms 1500 KB Output is correct
6 Correct 10 ms 1528 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 167 ms 14016 KB Output is correct
3 Correct 221 ms 9268 KB Output is correct
4 Correct 708 ms 27752 KB Output is correct
5 Correct 386 ms 28816 KB Output is correct
6 Correct 377 ms 27328 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 11 ms 1532 KB Output is correct
5 Correct 10 ms 1560 KB Output is correct
6 Correct 10 ms 1500 KB Output is correct
7 Correct 2 ms 292 KB Output is correct
8 Correct 168 ms 13988 KB Output is correct
9 Correct 220 ms 9224 KB Output is correct
10 Correct 708 ms 27768 KB Output is correct
11 Correct 386 ms 28824 KB Output is correct
12 Correct 376 ms 27252 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 170 ms 14056 KB Output is correct
15 Correct 41 ms 3320 KB Output is correct
16 Correct 732 ms 28040 KB Output is correct
17 Correct 380 ms 27412 KB Output is correct
18 Correct 381 ms 27532 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 10 ms 1548 KB Output is correct
6 Correct 10 ms 1528 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 168 ms 14012 KB Output is correct
9 Correct 221 ms 9200 KB Output is correct
10 Correct 712 ms 27768 KB Output is correct
11 Correct 393 ms 28816 KB Output is correct
12 Correct 391 ms 27300 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 171 ms 14040 KB Output is correct
15 Correct 42 ms 3228 KB Output is correct
16 Correct 724 ms 28028 KB Output is correct
17 Correct 381 ms 27476 KB Output is correct
18 Correct 381 ms 27448 KB Output is correct
19 Correct 1555 ms 224388 KB Output is correct
20 Correct 1527 ms 222136 KB Output is correct
21 Correct 1540 ms 224632 KB Output is correct
22 Correct 1546 ms 222016 KB Output is correct
23 Correct 1529 ms 222056 KB Output is correct
24 Correct 1531 ms 222104 KB Output is correct
25 Correct 1524 ms 222072 KB Output is correct
26 Correct 1536 ms 224764 KB Output is correct
27 Correct 1533 ms 224724 KB Output is correct
28 Correct 1541 ms 222160 KB Output is correct
29 Correct 1556 ms 222288 KB Output is correct
30 Correct 1527 ms 222072 KB Output is correct