oj.uz

Submission #171210

# Submission time Handle Problem Language Result Execution time Memory
171210 2019-12-27T19:09:59 Z CaroLinda Wall (IOI14_wall) C++14
61 / 100
 1863 ms 262144 KB 
	#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 && curL <= 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 " , scramble[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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 219504 KB Output is correct
2 Correct 197 ms 219652 KB Output is correct
3 Correct 230 ms 219592 KB Output is correct
4 Correct 201 ms 219976 KB Output is correct
5 Correct 216 ms 219924 KB Output is correct
6 Correct 204 ms 219896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 219508 KB Output is correct
2 Correct 356 ms 233184 KB Output is correct
3 Correct 362 ms 226920 KB Output is correct
4 Correct 1126 ms 238544 KB Output is correct
5 Correct 675 ms 239392 KB Output is correct
6 Correct 665 ms 237844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 219464 KB Output is correct
2 Correct 202 ms 219768 KB Output is correct
3 Correct 195 ms 219556 KB Output is correct
4 Correct 201 ms 220060 KB Output is correct
5 Correct 206 ms 219896 KB Output is correct
6 Correct 202 ms 219820 KB Output is correct
7 Correct 193 ms 219440 KB Output is correct
8 Correct 396 ms 233264 KB Output is correct
9 Correct 370 ms 226936 KB Output is correct
10 Correct 1148 ms 238480 KB Output is correct
11 Correct 672 ms 239504 KB Output is correct
12 Correct 658 ms 237828 KB Output is correct
13 Correct 194 ms 219524 KB Output is correct
14 Correct 367 ms 233212 KB Output is correct
15 Correct 219 ms 221036 KB Output is correct
16 Correct 700 ms 238752 KB Output is correct
17 Correct 645 ms 238104 KB Output is correct
18 Correct 644 ms 238000 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 219520 KB Output is correct
2 Correct 204 ms 219684 KB Output is correct
3 Correct 210 ms 219672 KB Output is correct
4 Correct 230 ms 219896 KB Output is correct
5 Correct 231 ms 219896 KB Output is correct
6 Correct 205 ms 219868 KB Output is correct
7 Correct 183 ms 219644 KB Output is correct
8 Correct 372 ms 233336 KB Output is correct
9 Correct 368 ms 226936 KB Output is correct
10 Correct 1195 ms 238628 KB Output is correct
11 Correct 666 ms 239436 KB Output is correct
12 Correct 660 ms 237944 KB Output is correct
13 Correct 191 ms 219524 KB Output is correct
14 Correct 372 ms 233248 KB Output is correct
15 Correct 226 ms 220940 KB Output is correct
16 Correct 703 ms 238852 KB Output is correct
17 Correct 649 ms 238264 KB Output is correct
18 Correct 643 ms 238140 KB Output is correct
19 Incorrect 1863 ms 262144 KB Output isn't correct
20 Halted 0 ms 0 KB -