oj.uz

Submission #927086

# Submission time Handle Problem Language Result Execution time Memory
927086 2024-02-14T08:51:42 Z Nurislam Wall (IOI14_wall) C++14
0 / 100
 113 ms 10320 KB 
//~ #include "wall.h"
#include <bits/stdc++.h>
//~ #include "grader.cpp"

using namespace std;

#define pb push_back
#define ff first
#define ss second
#define ll long long
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
const int N = 2e6+5;
pii b[N*4]{};pii inv = {0,0};
ll a[N]{};
void push(ll i, ll l, ll r){
	if(l == r){
		if(b[i].ss == 0)return;
		if(b[i].ss == 2){
			a[l] = min(b[i].ff, a[l]);
		}else{
			a[l] = max(b[i].ff, a[l]);
		}
		b[i] = {0,0};
		return;
	}
	b[i*2] = b[i];
	b[i*2+1] = b[i];
	b[i] = {0, 0};
}

void upd(ll i, ll l, ll r, ll tl, ll tr, pii val){
	if(l > tr || r < tl || r < l)return;
	if(tl <= l && r <= tr){
		b[i] = val;
		push(i, l, r);
		return;
	}
	ll m = (l+r)>>1;
	upd(i*2, l, m, tl, tr, val);
	upd(i*2+1, m+1, r, tl, tr, val);
	
}

int get(ll i, ll l, ll r, ll ps){
	if(b[i] != inv)push(i, l, r);
	if(l == r && l == ps)return a[ps];
	ll m = (l+r)>>1;
	if(ps <= m)return get(i*2, l, m, ps);
	else return get(i*2+1, m+1, r, ps);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int finalHeight[]){
	
	for(int i = 0; i < k; i++){
		upd(1, 0, n-1, l[i], r[i], {h[i], op[i]});
		//~ for(int i = 0; i < n; i++){
			//~ finalHeight[i] = get(1, 0, n-1, i);
			//~ cout << a[i] << ' ';
		//~ }cout << '\n';
	}
	for(int i = 0; i < n; i++){
		finalHeight[i] = get(1, 0, n-1, i);
		//~ cout << a[i] << ' ';
	}
	//~ cout << '\n';
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 113 ms 10320 KB Output is correct
3 Incorrect 101 ms 8016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -