Submission #127537

#	Time	Username	Problem	Language	Result	Execution time	Memory
127537		nxteru	Wall (IOI14_wall)	C++14	100 / 100	812 ms	162576 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 100001
#define PB push_back
struct node{
	int d,u;
	void ini(void){
		d=0,u=INF;
	}
	node operator +(const node &q)const{
		if(d>=q.u)return node{q.u,q.u};
		else if(u<=q.d)return node{q.d,q.d};
		else return node{max(d,q.d),min(u,q.u)};
	}
};
struct SEG{
	node seg[1<<20];
	SEG(void){
		for(int i=0;i<1<<20;i++){
			seg[i].ini();
		}
	}
	void up(int a,node x){
		a+=(1<<19)-1;
		seg[a]=x;
		while(a>0){
			a=(a-1)/2;
			seg[a]=seg[a*2+1]+seg[a*2+2];
		}
	}
	int que(void){
		return seg[0].d;
	}
};
SEG seg;
vector<int>in[2000005],out[2000005];
void buildWall(int n,int k,int t[],int l[],int r[],int h[],int ans[]){
	for(int i=0;i<k;i++)in[l[i]].PB(i),out[r[i]+1].PB(i);
	for(int i=0;i<n;i++){
		for(int j=0;j<in[i].size();j++){
			int x=in[i][j];
			node p;
			p.ini();
			if(t[x]==1)p.d=h[x];
			else p.u=h[x];
			seg.up(x,p);
		}
		for(int j=0;j<out[i].size();j++){
			node p;
			p.ini();
			seg.up(out[i][j],p);
		}
		ans[i]=seg.que();
	}
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<in[i].size();j++){
               ~^~~~~~~~~~~~~
wall.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<out[i].size();j++){
               ~^~~~~~~~~~~~~~

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