oj.uz

Submission #872588

# Submission time Handle Problem Language Result Execution time Memory
872588 2023-11-13T12:04:49 Z dsyz Wall (IOI14_wall) C++17
61 / 100
 615 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
#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 2 ms 560 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 6 ms 1880 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 5 ms 1912 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 114 ms 13908 KB Output is correct
3 Correct 127 ms 9796 KB Output is correct
4 Correct 433 ms 30756 KB Output is correct
5 Correct 220 ms 31876 KB Output is correct
6 Correct 220 ms 30476 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 6 ms 1884 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 111 ms 14004 KB Output is correct
9 Correct 135 ms 9812 KB Output is correct
10 Correct 431 ms 30936 KB Output is correct
11 Correct 217 ms 32020 KB Output is correct
12 Correct 214 ms 30464 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 114 ms 13928 KB Output is correct
15 Correct 29 ms 3672 KB Output is correct
16 Correct 551 ms 31480 KB Output is correct
17 Correct 233 ms 30580 KB Output is correct
18 Correct 231 ms 30536 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 528 KB Output is correct
4 Correct 6 ms 1728 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 5 ms 1952 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 115 ms 13920 KB Output is correct
9 Correct 122 ms 9792 KB Output is correct
10 Correct 383 ms 30844 KB Output is correct
11 Correct 240 ms 31876 KB Output is correct
12 Correct 213 ms 30292 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 116 ms 13956 KB Output is correct
15 Correct 33 ms 3888 KB Output is correct
16 Correct 533 ms 31200 KB Output is correct
17 Correct 245 ms 30472 KB Output is correct
18 Correct 231 ms 30588 KB Output is correct
19 Runtime error 615 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -