Submission #171206

#	Time	Username	Problem	Language	Result	Execution time	Memory
171206		CaroLinda	Wall (IOI14_wall)	C++14	0 / 100	3053 ms	233188 KiB

wall

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

	#define debug 
	#define lp(i,a,b) for(int i = a ; i < b ; i++ )
	#define ff first
	#define ss second
	#define pb push_back
	#define mk make_pair
	#define ll long long
	#define sz size()
	#define pii pair<int,int>
	#define all(x) x.begin(),x.end()
	#define tiii tuple<int,int,int, int>
	#define mkt make_tuple

	const int MAXN = 2e6+10 , inf = 1e9+10 ;

	using namespace std ;

	struct Seg
	{

		struct Node
		{

			int lef , rig, mxLef , mnRig ;
			bool locked ;

			Node() 
			{
				lef = mxLef =-inf , rig = mnRig =  inf ;
				locked = false ;
			}

		} ;

		Node tree[MAXN*4] ;

		int m(int l, int r) { return (l+r)>>1 ; }

		void merge(int pos, int l, int r)
		{

			tree[pos].mxLef = tree[pos].lef ;
			tree[pos].mnRig =tree[pos].rig ;

			tree[pos].mxLef = max(tree[pos].mxLef, max( tree[pos*2].mxLef, tree[pos*2+1].mxLef ) ) ;
			tree[pos].mnRig = min( tree[pos].mnRig , min(tree[pos*2].mnRig, tree[pos*2+1].mnRig )) ;

		}

		void check(int pos, int l, int r, int curL, int curR , vector<int> &List )
		{

			if( tree[pos].locked ) return ;

			curL = max( curL, tree[pos].lef ) ;
			curR = min( curR, tree[pos].rig ) ;

			if( tree[pos].mnRig >= curL && tree[pos].mxLef <= curR )
				return ;

			if( l == r ) 
			{
				List.pb(l) ;
				tree[pos].locked = true ;
				tree[pos].lef = -inf ;
				tree[pos].rig = inf ;
				return ;
			}

			check(pos*2,l,m(l,r), curL, curR , List ) ;
			check(pos*2+1,m(l,r)+1, r, curL, curR, List ) ;

			if( tree[pos*2].locked && tree[pos*2+1].locked )
			{
				tree[pos].locked = true ;
				tree[pos].lef = -inf ;
				tree[pos].rig = inf ;
			}

		}

		void upd(int pos, int l, int r, int beg, int en ,int num, int type, int curL, int curR, vector<int> &v )
		{

			if( tree[pos].locked || r < beg || l > en ) return ;
			curL = max(curL, tree[pos].lef ) ;
			curR = min( curR, tree[pos].rig ) ;
			if( l >= beg && r <= en )
			{
				if( type == 1 ) tree[pos].lef = max( tree[pos].lef, num ) ;
				else tree[pos].rig = min( tree[pos].rig, num ) ;
				merge(pos,l,r) ;
				check(pos,l,r,curL,curR, v) ;
				return ;
			}

			upd(pos*2,l,m(l,r),beg, en, num ,type, curL, curR,v) ;
			upd(pos*2+1,m(l,r)+1, r, beg, en , num , type , curL, curR,v ) ;

			merge(pos,l,r) ;

		}

		void print(int pos, int l, int r, int curL, int curR)
		{
			curL = max(curL, tree[pos].lef ) ;
			curR = min( curR, tree[pos].rig ) ;
			if(l == r) return (void)(printf("%d -> %d %d\n" , l , curL, curR)) ;
			print(pos*2,l,m(l,r), curL, curR ) ;
			print(pos*2+1,m(l,r)+1, r, curL, curR ) ;
		}

	} ;

	struct secondSeg
	{

		struct Node
		{

			int lef, rig ;

			Node() { lef = -inf , rig = inf ; }

		} ;

		Node v[MAXN*4] ;

		int m(int l, int r) { return (l+r)>>1 ; }

		void upd(int pos, int l, int r, int beg, int en,int num, int type )
		{

			if( l > en || r < beg ) return ;
			if( l >= beg && r <= en )
			{
				if(type==1) v[pos].lef = max(v[pos].lef, num) ;
				else v[pos].rig = min(v[pos].rig, num) ; 
				return ;
			}

			upd(pos*2,l,m(l,r),beg,en,num,type) ;
			upd(pos*2+1,m(l,r)+1, r, beg, en , num , type ) ;

		}

		void qry(int pos, int l, int r, int &curL, int &curR , int idx )
		{
			curL = max(curL, v[pos].lef ) ;
			curR = min(curR, v[pos].rig ) ;
			if( l == r ) return ;
			if( idx <= m(l,r) ) qry(pos*2,l,m(l,r), curL, curR , idx ) ;
			else qry(pos*2+1, m(l,r)+1, r, curL, curR , idx ) ;
		}

	} ;

	int scramble[MAXN] , idx[MAXN] ;
	Seg seg ;
	secondSeg seg2 ;

	bool cmp(int i, int j) { return scramble[i] < scramble[j] ; }

	void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
	{

		reverse(op,op+k) ;
		reverse(right, right+k) ;
		reverse(left, left+k) ;
		reverse(height, height+k) ;

		vector<int> aux ;
		lp(i,0,n) scramble[i] = inf ;

		lp(i,0,k)
		{

			aux.clear() ;
			seg.upd(1,0,n-1,left[i], right[i] , height[i] , op[i], -inf, inf, aux ) ;
			for(int j : aux ) scramble[j] = i ;

		}

		iota(idx, idx+n,0 ) ;
		sort(idx, idx+n , cmp ) ;

		lp(i,0,n) debug("%d " , idx[i] ) ;
		debug("\n") ;

		int curIdx = 0 ;

		lp(i,0,k)
		{

			seg2.upd( 1 , 0 , n-1 , left[i] , right[i] , height[i] , op[i] ) ;
			while(curIdx < n && scramble[ idx[curIdx] ] == i+1 )
			{

				debug("Processing %d\n", idx[curIdx] ) ;

				int curL = -inf , curR = inf ;
				seg2.qry( 1 , 0 , n-1 , curL , curR , idx[curIdx] ) ;
				if( op[i+1] == 1 ) finalHeight[ idx[curIdx] ] = curR ;
				else finalHeight[ idx[curIdx] ] = curL ;

				curIdx ++ ;

			}

		}

		lp(i,0,n)
			if( scramble[i] == inf )
			{
				finalHeight[i] = 0;
				int curR = inf ;
				seg2.qry( 1 , 0 , n-1 , finalHeight[i], curR, i ) ;
			}

		return ;

	}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:190:32: warning: left operand of comma operator has no effect [-Wunused-value]
   lp(i,0,n) debug("%d " , idx[i] ) ;
                                ^
wall.cpp:191:15: warning: statement has no effect [-Wunused-value]
   debug("\n") ;
               ^
wall.cpp:202:40: warning: left operand of comma operator has no effect [-Wunused-value]
     debug("Processing %d\n", idx[curIdx] ) ;
                                        ^

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