oj.uz

Submission #1006350

# Submission time Handle Problem Language Result Execution time Memory
1006350 2024-06-23T20:05:27 Z NintsiChkhaidze Wall (IOI14_wall) C++17
0 / 100
 151 ms 262144 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;
vector <pii> lz[4*N];
pii t[4*N];

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

void push(int h){
	if (!lz[h].size()) return;
	for (auto [H,tp]: lz[h]){
		chn(h*2,H,tp);
		chn(h*2+1,H,tp);
		lz[h*2].pb({H,tp});
		lz[h*2+1].pb({H,tp});
	}
	lz[h].clear();
}

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){
		if (tp == 1){
			//max -> H
			if (t[h].f < H){
				t[h].f = H;
				t[h].s = max(t[h].s,H);
			}
		}else{
			//min -> H
			if (t[h].s > H){
				t[h].s = H;
				t[h].f = min(t[h].f,H);
			}
		}
		lz[h].pb({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 buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
  for (int i = 0; i < k; i++){
  	left[i]++;
  	right[i]++;
	upd(1,1,n,left[i],right[i],height[i],op[i]);
  }
  
  for (int i = 0; i < n; i++){
  	finalHeight[i] = get(1,1,n,i+ 1);
  }
  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 189020 KB Output is correct
2 Correct 38 ms 189264 KB Output is correct
3 Correct 35 ms 191312 KB Output is correct
4 Runtime error 108 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 189012 KB Output is correct
2 Correct 115 ms 202172 KB Output is correct
3 Runtime error 151 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 189020 KB Output is correct
2 Correct 30 ms 189264 KB Output is correct
3 Correct 33 ms 191320 KB Output is correct
4 Runtime error 126 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 189140 KB Output is correct
2 Correct 35 ms 189268 KB Output is correct
3 Correct 38 ms 191320 KB Output is correct
4 Runtime error 124 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -