Submission #287111

#	Time	Username	Problem	Language	Result	Execution time	Memory
287111		AKaan37	Wall (IOI14_wall)	C++17	61 / 100	1175 ms	41208 KiB

wall

//Bismillahirrahmanirrahim

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

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 2000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,tree[li*4],lazy[li*4],lazy1[li*4];
int cev;
string s;
vector<int> v;

inline void push1(int node,int start,int end){
	//~ if(start==end)cout<<lazy[node]<<"**\n";
	if(lazy[node]==0)return;
	tree[node]=max(tree[node],lazy[node]);
	if(start!=end){
		lazy[node*2] = max(lazy[node*2],lazy[node]),lazy1[node*2] = max(lazy1[node*2],lazy[node]);
        lazy[node*2+1] = max(lazy[node*2+1],lazy[node]),lazy1[node*2+1] = max(lazy1[node*2+1],lazy[node]);
        lazy1[node*2] = min(lazy1[node*2],lazy1[node]),lazy[node*2] = min(lazy[node*2],lazy1[node]);
        lazy1[node*2+1] = min(lazy1[node*2+1],lazy1[node]),lazy[node*2+1] = min(lazy[node*2+1],lazy1[node]);
	}
	lazy[node]=0;
}

inline void push2(int node,int start,int end){
	//~ cout<<lazy1[node]<<endl;
	if(lazy1[node]==inf)return;
	tree[node]=min(tree[node],lazy1[node]);
	//~ if(lazy[node]>lazy1[node])lazy[node]=lazy1[node];
	if(start!=end){
		lazy[node*2] = max(lazy[node*2],lazy[node]),lazy1[node*2] = max(lazy1[node*2],lazy[node]);
        lazy[node*2+1] = max(lazy[node*2+1],lazy[node]),lazy1[node*2+1] = max(lazy1[node*2+1],lazy[node]);
        lazy1[node*2] = min(lazy1[node*2],lazy1[node]),lazy[node*2] = min(lazy[node*2],lazy1[node]);
        lazy1[node*2+1] = min(lazy1[node*2+1],lazy1[node]),lazy[node*2+1] = min(lazy[node*2+1],lazy1[node]);
	}
	lazy1[node]=inf;
}

inline void update(int node,int start,int end,int l,int r,int val){
	push2(node,start,end);push1(node,start,end);
	
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy[node]=val;
		
		push1(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline void update1(int node,int start,int end,int l,int r,int val){
	push2(node,start,end);push1(node,start,end);
	
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy1[node]=val;
		push2(node,start,end);
		return ;
	}
	update1(node*2,start,mid,l,r,val),update1(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	push2(node,start,end);push1(node,start,end);
	
	if(start>=l && end<=r)return tree[node];
	return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1;i<=n*4;i++){
		lazy1[i]=inf;
	}
	for(int i=0;i<k;i++){
		if(op[i]==1){
			update(1,1,n,left[i]+1,right[i]+1,height[i]);
		}
		else update1(1,1,n,left[i]+1,right[i]+1,height[i]);
	}
	//~ cout<<query(1,1,n,1,1);
	FOR finalHeight[i-1]=query(1,1,n,i,i);
	return;
}

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