Submission #901981

#	Time	Username	Problem	Language	Result	Execution time	Memory
901981		MuhammadSaram	Wall (IOI14_wall)	C++17	61 / 100	3050 ms	248448 KiB

wall

#include <bits/stdc++.h>

using namespace std;

const int M = 5e5, inf = 1e6;

int seg[2][M*4],k;

void modify(int ty,int p,int x,int v=1,int s=0,int e=k)
{
	if (s+1==e)
	{
		seg[ty][v]=x;
		return;
	}
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	if (p<mid)
		modify(ty,p,x,lc,s,mid);
	else
		modify(ty,p,x,rc,mid,e);
	if (ty)
		seg[ty][v]=min(seg[ty][lc],seg[ty][rc]);
	else
		seg[ty][v]=max(seg[ty][lc],seg[ty][rc]);
}

int get(int ty,int l,int r,int v=1,int s=0,int e=k)
{
	if (r<=s or e<=l)
		return ty*inf;
	if (l<=s and e<=r)
		return seg[ty][v];
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	if (ty)
		return min(get(ty,l,r,lc,s,mid),get(ty,l,r,rc,mid,e));
	return max(get(ty,l,r,lc,s,mid),get(ty,l,r,rc,mid,e));
}

void buildWall(int n, int K, int op[], int left[], int right[], int height[], int finalHeight[])
{
	k=K;
	for (int i=0;i<k;i++)
		for (int j=0;j<2;j++)
			modify(j,i,j*inf);
	vector<pair<int,int>> st[2][n],en[2][n];
	for (int i=0;i<k;i++)
	{
		st[op[i]-1][left[i]].push_back({i,height[i]});
		en[op[i]-1][right[i]].push_back({i,height[i]});
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<2;j++)
			for (auto x:st[j][i])
				modify(j,x.first,x.second);
		int s=-1,e=k;
		while (s+1<e)
		{
			int mid=(s+e)/2;
			int x=get(0,mid,k),y=get(1,mid,k);
			if (x>y)
				s=mid;
			else
				e=mid;
		}
		if (s==-1)
			finalHeight[i]=get(0,0,k);
		else
		{
			int x=get(0,s,k),y=get(1,s,k);
			int x1=get(0,s+1,k),y1=get(1,s+1,k);
			if (x==x1)
				finalHeight[i]=x;
			else
				finalHeight[i]=y;
		}
		for (int j=0;j<2;j++)
			for (auto x:en[j][i])
				modify(j,x.first,inf*j);
	}
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:71:24: warning: unused variable 'y1' [-Wunused-variable]
   71 |    int x1=get(0,s+1,k),y1=get(1,s+1,k);
      |                        ^~

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