oj.uz

Submission #1006362

# Submission time Handle Problem Language Result Execution time Memory
1006362 2024-06-23T20:49:18 Z NintsiChkhaidze Wall (IOI14_wall) C++17
100 / 100
 498 ms 61200 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define pii pair <int,int>
#define f first
#define s second
#define pb push_back
#define leftt h*2,l,(l + r)/2
#define rightt h*2+1,(l + r)/2 + 1,r
using namespace std;

const int N = 2e6 + 3,inf = 1e9;
pii t[4*N],lz[4*N];

void chn(int h,int H,int tp){
	if (tp == 1){
		t[h].f = max(t[h].f,H);
		t[h].s = max(t[h].s,H);
	}else{
		t[h].f = min(t[h].f,H);
		t[h].s = min(t[h].s,H);
	}
}

void push(int h){
	if (t[h].f == 0 && t[h].s == inf) return;
	
	chn(h*2,t[h].f,1);
	chn(h*2,t[h].s,2);
	chn(h*2+1,t[h].f,1);
	chn(h*2+1,t[h].s,2);
	
	t[h] = {0,inf};
}

void upd(int h,int l,int r,int L,int R,int H,int tp){
	if (r < L || R < l) return ;
	if (L <= l && r <= R){
		chn(h,H,tp);
		return;
	}
	
	push(h);
	upd(leftt,L,R,H,tp);
	upd(rightt,L,R,H,tp);
}

int get(int h,int l,int r,int idx){
	if (l == r) return t[h].f;
	push(h);
	if (idx > (l + r)/2) return get(rightt,idx);
	return get(leftt,idx);
}

void build(int h,int l,int r){
	t[h] = {0,inf};
	if (l == r) return;
	build(leftt);
	build(rightt);
}

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 77 ms 10216 KB Output is correct
3 Correct 104 ms 5684 KB Output is correct
4 Correct 298 ms 12976 KB Output is correct
5 Correct 150 ms 13400 KB Output is correct
6 Correct 137 ms 13392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 89 ms 10164 KB Output is correct
9 Correct 105 ms 5712 KB Output is correct
10 Correct 287 ms 12880 KB Output is correct
11 Correct 158 ms 13392 KB Output is correct
12 Correct 159 ms 13392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 84 ms 10280 KB Output is correct
15 Correct 18 ms 2904 KB Output is correct
16 Correct 307 ms 13056 KB Output is correct
17 Correct 146 ms 13136 KB Output is correct
18 Correct 192 ms 12972 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 77 ms 10200 KB Output is correct
9 Correct 104 ms 5648 KB Output is correct
10 Correct 274 ms 12840 KB Output is correct
11 Correct 145 ms 13328 KB Output is correct
12 Correct 146 ms 13304 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 78 ms 10152 KB Output is correct
15 Correct 18 ms 2908 KB Output is correct
16 Correct 299 ms 13020 KB Output is correct
17 Correct 158 ms 13140 KB Output is correct
18 Correct 161 ms 12988 KB Output is correct
19 Correct 498 ms 61076 KB Output is correct
20 Correct 444 ms 58796 KB Output is correct
21 Correct 447 ms 61200 KB Output is correct
22 Correct 412 ms 58708 KB Output is correct
23 Correct 417 ms 58752 KB Output is correct
24 Correct 415 ms 58772 KB Output is correct
25 Correct 436 ms 58708 KB Output is correct
26 Correct 457 ms 61168 KB Output is correct
27 Correct 431 ms 61084 KB Output is correct
28 Correct 457 ms 58732 KB Output is correct
29 Correct 446 ms 58708 KB Output is correct
30 Correct 425 ms 58536 KB Output is correct