oj.uz

Submission #171213

# Submission time Handle Problem Language Result Execution time Memory
171213 2019-12-27T19:12:28 Z CaroLinda Wall (IOI14_wall) C++14
61 / 100
 1878 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 = 2e9+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 ) ;

		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 )
			{

				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 ;

	}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 219640 KB Output is correct
2 Correct 194 ms 219744 KB Output is correct
3 Correct 212 ms 219512 KB Output is correct
4 Correct 199 ms 219896 KB Output is correct
5 Correct 203 ms 219896 KB Output is correct
6 Correct 202 ms 219896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 219512 KB Output is correct
2 Correct 368 ms 232756 KB Output is correct
3 Correct 372 ms 226808 KB Output is correct
4 Correct 1220 ms 232540 KB Output is correct
5 Correct 671 ms 232824 KB Output is correct
6 Correct 659 ms 232648 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 219440 KB Output is correct
2 Correct 196 ms 219640 KB Output is correct
3 Correct 195 ms 219636 KB Output is correct
4 Correct 210 ms 220024 KB Output is correct
5 Correct 203 ms 219852 KB Output is correct
6 Correct 202 ms 219872 KB Output is correct
7 Correct 195 ms 219512 KB Output is correct
8 Correct 360 ms 229496 KB Output is correct
9 Correct 369 ms 225784 KB Output is correct
10 Correct 1115 ms 230096 KB Output is correct
11 Correct 672 ms 230264 KB Output is correct
12 Correct 656 ms 230008 KB Output is correct
13 Correct 193 ms 219648 KB Output is correct
14 Correct 368 ms 228344 KB Output is correct
15 Correct 221 ms 220920 KB Output is correct
16 Correct 722 ms 229672 KB Output is correct
17 Correct 644 ms 229568 KB Output is correct
18 Correct 638 ms 229368 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 219604 KB Output is correct
2 Correct 195 ms 219612 KB Output is correct
3 Correct 196 ms 219648 KB Output is correct
4 Correct 200 ms 219896 KB Output is correct
5 Correct 203 ms 219932 KB Output is correct
6 Correct 204 ms 219896 KB Output is correct
7 Correct 194 ms 219640 KB Output is correct
8 Correct 370 ms 227964 KB Output is correct
9 Correct 370 ms 223992 KB Output is correct
10 Correct 1110 ms 229492 KB Output is correct
11 Correct 674 ms 229564 KB Output is correct
12 Correct 656 ms 229576 KB Output is correct
13 Correct 192 ms 219512 KB Output is correct
14 Correct 366 ms 227892 KB Output is correct
15 Correct 222 ms 220892 KB Output is correct
16 Correct 694 ms 229524 KB Output is correct
17 Correct 648 ms 229532 KB Output is correct
18 Correct 641 ms 229496 KB Output is correct
19 Incorrect 1878 ms 262144 KB Output isn't correct
20 Halted 0 ms 0 KB -