Submission #645925

#	Time	Username	Problem	Language	Result	Execution time	Memory
645925		beaconmc	벽 (IOI14_wall)	C++14	0 / 100	224 ms	262144 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll tree[4194304];
vector<ll> lazy[4194304];
ll N = 2097152;
vector<ll> ans;

void prop(ll pos, ll mini, ll maxi){
	if (maxi>= lazy[pos][0]){
		lazy[pos][0] = maxi;
		lazy[pos][1] = maxi;
	}else{
		lazy[pos][1] = max(maxi, lazy[pos][1]);
	}

	if (mini<= lazy[pos][1]){
		lazy[pos][0] = mini;
		lazy[pos][1] = mini;
	}else{
		lazy[pos][0] = min(mini, lazy[pos][0]);
	}
}

void update(ll a, ll b, ll op, ll val, ll k=1, ll x=0, ll y=N-1){
	if (b<x || a>y) return;
	if (a<=x && y<=b){
		if(op){
			if (val >= lazy[k][0]){
				lazy[k][0] = val;
				lazy[k][1] = val;
			}else{
				lazy[k][1] = max(lazy[k][1],val);
			}
		}else{
			if (val <= lazy[k][1]){
				lazy[k][0] = val;
				lazy[k][1] = val;
			}else{
				lazy[k][0] = min(lazy[k][0],val);
			}
		}
		return;
	}
    prop(k*2,lazy[k][0],lazy[k][1]);
    prop(k*2+1,lazy[k][0],lazy[k][1]);
    lazy[k] = {1000000000,-1};
    ll d = (x+y)/2;
    update(a,b,op,val,2*k,x,d);
    update(a,b,op,val,2*k+1,d+1,y);
    return;

}

void propagate(){
	FOR(i,1,N){
		prop(i*2, lazy[i][0],lazy[i][1]);
        prop(i*2+1, lazy[i][0],lazy[i][1]);
	}
	FOR(i,N,2*N){
		tree[i] = min(tree[i], lazy[i][0]);
        tree[i] = max(tree[i], lazy[i][1]);
        ans.push_back(tree[i]);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	FOR(i,0,1048576){
		tree[i] = 0;
		lazy[i] = {1000000000,-1};
	}
	FOR(i,0,k){
		if (op[i]==2) op[i] = 0;
		update(left[i], right[i], op[i], height[i]);
	}
	propagate();
	FOR(i,0,n){
		finalHeight[i] = ans[i];
	}
}

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