Submission #1039209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039209		mateuszwes	Wall (IOI14_wall)	C++17	0 / 100	16 ms	33352 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define F first
#define S second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pq priority_queue
 
using namespace std;
constexpr int debug = 1;
constexpr int N = 2e6+7;
constexpr int M = 1e5+7;
constexpr int base = 1<<21;

int l, r;
pi tree[2*base+7], tree2[2*base+7];		//min, maks

//if new min smaller then keep unchanged
//if new min > old min then adjust min
//if new min > max then max = min
//etc
//these changes are ok because they include the time

void mini(int git, int v){
	if(git == -1) return;
	if(git > tree[v].F){
		tree[v].F = tree2[v].F = git;
		if(git > tree[v].S){
			tree[v].S = tree2[v].S = git;
		}
	}
}

void maxi(int git, int v){
	if(git == -1) return;
	if(git < tree[v].S){
		tree[v].S = tree2[v].S = git;
		if(git < tree[v].F){
			tree[v].S = tree2[v].S = git;
		}
	}
}

void push(int v){
	mini(tree2[v].F, 2*v);
	maxi(tree2[v].F, 2*v);
	mini(tree2[v].S, 2*v+1);
	maxi(tree2[v].S, 2*v+1);
	tree2[v] = {-1, -1};
}

void change(int v, int operation, int val, int a, int b){
	if((b < l) || (a > r)) return;
	else if((a >= l) && (b <= r)){
		if(operation == 1){
			mini(val, v);
		}
		else{
			maxi(val, v);
		}
	}
	else{
		int mid = (a+b)/2;
		push(v);
		change(2*v, operation, val, a, mid);
		change(2*v+1, operation, val, mid+1, b);
		tree[v] = {min(tree[2*v].F, tree[2*v+1].F), max(tree[2*v].S, tree[2*v+1].S)};
	}
}

int read(int i, int v, int a, int b){
	if((b < i) || (a > i)) return -1;
	else if((a >= i) && (b <= i)){
		return tree[v].F;
	}
	else{
		int mid = (a+b)/2;
		push(v);
		int sc = read(i, 2*v, a, mid);
		if(sc == -1) return read(i, 2*v+1, mid+1, b);
		return sc;
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	fill(finalHeight, finalHeight+n, 0);
  	for(int i = 0; i < 2*base+7; i++) tree2[i] = {-1, -1};
  	//1 is for adding
  	for(int i = 0; i < k; i++){
  		l = left[i];
  		r = right[i];
  		change(1, op[i], height[i], 0, base-1);
  	}

  	for(int i = 0; i < n; i++){
  		finalHeight[i] = read(i, 1, 0, base-1);
  		if(debug) cout << finalHeight[i] << '\n';
  	}
}

/*
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int ok[] = {1, 2, 2, 1, 1, 2};
	int lel[] = {1, 4, 3, 0, 2, 6};
	int rer[] = {8, 9, 6, 5, 2, 7};
	int heh[] = {4, 1 ,5, 3, 5 ,0};
	int fif[] = {0, 0, 0, 0, 0, 0};
	buildWall(10, 6, ok[], lel[], rer[], heh[], fif[]);
	
	return 0;
}
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39