Submission #920518

#	Time	Username	Problem	Language	Result	Execution time	Memory
920518		Nika533	Wall (IOI14_wall)	C++17	100 / 100	581 ms	163352 KiB

wall

#pragma GCC diagnostic warning "-std=c++11"

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

#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>

using namespace std;

const int N=2e6+5,K=5e5+5;

pii t[K*4];
vector<int> L[N],R[N];

pii merge(pii a, pii b) {
	pii c;
	if (b.f==-1) return b;
	if (a.f==-1) {
		c.f=-1;
		if (a.s<b.f) c.s=b.f;
		else if (a.s>b.s) c.s=b.s;
		else c.s=a.s;
		return c;
	}
	int l=max(a.f,b.f),r=min(a.s,b.s);
	if (l<=r) return {l,r};
	if (a.s<b.s) return {-1,b.f};
	else return {-1,b.s};
}

void update(int v, int tl, int tr, int ind, int x, int y) {
	if (tl==tr) {
		t[v]={x,y};
		return;
	}
	int mid=(tl+tr)/2;
	if (ind<=mid) update(v*2,tl,mid,ind,x,y);
	else update(v*2+1,mid+1,tr,ind,x,y);
	t[v]=merge(t[v*2],t[v*2+1]);
}

pii query(int v, int tl, int tr, int l, int r) {
	if (tl==l && tr==r) return t[v];
	int mid=(tl+tr)/2;
	if (r<=mid) return query(v*2,tl,mid,l,r);
	else if (mid+1<=l) return query(v*2+1,mid+1,tr,l,r);
	else return merge(query(v*2,tl,mid,l,mid),query(v*2+1,mid+1,tr,mid+1,r));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	for (int i=0; i<k; i++) {
		L[left[i]].pb(i);
		R[right[i]].pb(i);
	}
	
	for (int i=0; i<k; i++) update(1,0,k-1,i,0,1e9);
	
	for (int i=0; i<n; i++) {
		
//		cout<<"I "<<i<<endl;
//		
//		for (int i=0; i<k*4; i++) {
//			cout<<"TTT "<<i<<" "<<t[i].f<<" "<<t[i].s<<endl;
//		}
		
		if (i) {
			for (auto x:R[i-1]) {
				update(1,0,k-1,x,0,1e9);
			}
		}
		
		for (auto x:L[i]) {
			if (op[x]==1) update(1,0,k-1,x,height[x],1e9);
			else update(1,0,k-1,x,0,height[x]);
		}
		
		pii ans=query(1,0,k-1,0,k-1);
		
		if (ans.f==-1) finalHeight[i]=ans.s;
		else finalHeight[i]=ans.f;
	}
}

Compilation message (stderr)

wall.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~

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