oj.uz

Submission #872589

# Submission time Handle Problem Language Result Execution time Memory
872589 2023-11-13T12:05:51 Z dsyz Wall (IOI14_wall) C++17
100 / 100
 811 ms 224780 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
#define MAXN (1000005)

struct node {
	node *l, *r;
	ll s,e,m,opmax,opmin;
	node(ll _s,ll _e){
		s=_s,e=_e,m=(s+e)/2;
		opmax = opmin = 0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void minimise(ll x,ll y,ll nval){
		value();
		if(s==x&&e==y) {
			if(opmax > nval) {
				opmax = nval;
				if(opmin > nval)opmin=nval;
			}
			return;
		}
		if(x>m)r->minimise(x,y,nval);
		else if(y<=m)l->minimise(x,y,nval);
		else l->minimise(x,m,nval),r->minimise(m+1,y,nval);
		opmax = max(l->opmax, r->opmax);
		opmin = min(l->opmin, r->opmin);
	}
	void maximise(ll x,ll y,ll nval){
		value();
		if(s==x&&e==y) {
			if(opmin < nval) {
				opmin = nval;
				if(opmax < nval)opmax=nval;
			}
			return;
		}
		if(x>m)r->maximise(x,y,nval);
		else if(y<=m)l->maximise(x,y,nval);
		else l->maximise(x,m,nval),r->maximise(m+1,y,nval);
		opmax = max(l->opmax, r->opmax);
		opmin = min(l->opmin, r->opmin);
	}
	void value() {
		if(s==e) return;
		if(opmin > l->opmin || opmin > r->opmin) {
			l->opmin=max(l->opmin, opmin);
			r->opmin=max(r->opmin, opmin);
			if(l->opmax < l->opmin) l->opmax = l->opmin;
			if(r->opmax < r->opmin) r->opmax = r->opmin;
		}
		if(opmax < l->opmax || opmax < r->opmax) {
			l->opmax=min(l->opmax, opmax);
			r->opmax=min(r->opmax, opmax);
			if(l->opmax < l->opmin) l->opmin = l->opmax;
			if(r->opmax < r->opmin) r->opmin = r->opmax;
		}
	}
	ll query(ll x){
		value();
		if(s==e) {
			assert(opmin==opmax);
			return opmin;
		}
		if(x>m)return r->query(x);
		else return l->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(ll i = 0;i < k;i++){
		if(op[i] == 1){
			root -> maximise(left[i],right[i],height[i]);
		}else if(op[i] == 2){
			root -> minimise(left[i],right[i],height[i]);
		}
	}
	for(ll i = 0;i < n;i++){
		finalHeight[i] = root -> query(i);
	}
	return;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 109 ms 8080 KB Output is correct
3 Correct 125 ms 5460 KB Output is correct
4 Correct 365 ms 18032 KB Output is correct
5 Correct 214 ms 18772 KB Output is correct
6 Correct 201 ms 18684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 8192 KB Output is correct
9 Correct 147 ms 5404 KB Output is correct
10 Correct 359 ms 18000 KB Output is correct
11 Correct 203 ms 18572 KB Output is correct
12 Correct 200 ms 18676 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 110 ms 8064 KB Output is correct
15 Correct 28 ms 2652 KB Output is correct
16 Correct 487 ms 18256 KB Output is correct
17 Correct 209 ms 18260 KB Output is correct
18 Correct 222 ms 18492 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 4 ms 1368 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 106 ms 8020 KB Output is correct
9 Correct 117 ms 5480 KB Output is correct
10 Correct 365 ms 18260 KB Output is correct
11 Correct 211 ms 18512 KB Output is correct
12 Correct 200 ms 18512 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 116 ms 8388 KB Output is correct
15 Correct 28 ms 2536 KB Output is correct
16 Correct 542 ms 18312 KB Output is correct
17 Correct 218 ms 18260 KB Output is correct
18 Correct 213 ms 18296 KB Output is correct
19 Correct 811 ms 224480 KB Output is correct
20 Correct 786 ms 222076 KB Output is correct
21 Correct 751 ms 224496 KB Output is correct
22 Correct 789 ms 222376 KB Output is correct
23 Correct 767 ms 222288 KB Output is correct
24 Correct 753 ms 222016 KB Output is correct
25 Correct 757 ms 222028 KB Output is correct
26 Correct 783 ms 224780 KB Output is correct
27 Correct 801 ms 224480 KB Output is correct
28 Correct 763 ms 221984 KB Output is correct
29 Correct 775 ms 222132 KB Output is correct
30 Correct 804 ms 222168 KB Output is correct