Submission #88412

#	Time	Username	Problem	Language	Result	Execution time	Memory
88412		Pajaraja	Wall (IOI14_wall)	C++17	0 / 100	2 ms	692 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
pair<int,int> seg[4*MAXN];
bool a[4*MAXN];
int poz[MAXN];
void loc(int l,int r,int ind)
{
	if(l==r) {poz[l]=ind; return;}
	int s=(l+r)/2; loc(l,s,2*ind); loc(s+1,r,2*ind+1);
}
void upd(int l,int r,int lt, int rt,int val,bool b,int x,int ind)
{
	if(r<lt || l>rt) return;
	if(l>=lt && r<=rt)
	{
		if(b) seg[ind].second=max(seg[ind].second,val);
		else seg[ind].second=min(seg[ind].second,val);
		seg[ind].first=x;
		a[ind]=b;
		return;
	}
	int s=(l+r)/2;
	upd(l,s,lt,rt,val,b,x,2*ind); upd(s+1,r,lt,rt,val,b,x,2*ind+1); 
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	loc(0,n-1,1);
	for(int i=0;i<k;i++) upd(0,n-1,left[i],right[i],height[i],op[i]==1,i,1);
	for(int i=0;i<n;i++) 
	{
		vector<pair<pair<int,int>,bool> > arr;
		while(poz[i]!=0) {if(seg[poz[i]].first!=0) arr.push_back(make_pair(seg[poz[i]],a[poz[i]])); poz[i]/=2;}
		sort(arr.begin(),arr.end());
		if(arr.size()>0) finalHeight[i]=arr[0].first.second;
		for(int j=1;j<arr.size();j++) {if(arr[j].second) finalHeight[i]=max(finalHeight[i],arr[j].first.second); else finalHeight[i]=min(finalHeight[i],arr[j].first.second);}
	}
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<arr.size();j++) {if(arr[j].second) finalHeight[i]=max(finalHeight[i],arr[j].first.second); else finalHeight[i]=min(finalHeight[i],arr[j].first.second);}
               ~^~~~~~~~~~~

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