oj.uz

답안 #171219

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171219 2019-12-27T19:50:29 Z CaroLinda 벽 (IOI14_wall) C++14
61 / 100
 1584 ms 262148 KB 
	#include "wall.h"
	#include <bits/stdc++.h>

	#define debug printf
	#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 = 2100000 , 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] ] = max(0,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

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 230476 KB Output is correct
2 Correct 203 ms 230648 KB Output is correct
3 Correct 203 ms 230648 KB Output is correct
4 Correct 208 ms 231004 KB Output is correct
5 Correct 210 ms 230776 KB Output is correct
6 Correct 209 ms 230748 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 230420 KB Output is correct
2 Correct 377 ms 239736 KB Output is correct
3 Correct 379 ms 235412 KB Output is correct
4 Correct 1102 ms 241692 KB Output is correct
5 Correct 681 ms 242040 KB Output is correct
6 Correct 664 ms 241836 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 230444 KB Output is correct
2 Correct 204 ms 230628 KB Output is correct
3 Correct 206 ms 230536 KB Output is correct
4 Correct 210 ms 230928 KB Output is correct
5 Correct 223 ms 231024 KB Output is correct
6 Correct 213 ms 230748 KB Output is correct
7 Correct 215 ms 230392 KB Output is correct
8 Correct 378 ms 240248 KB Output is correct
9 Correct 375 ms 236156 KB Output is correct
10 Correct 1107 ms 241220 KB Output is correct
11 Correct 730 ms 241540 KB Output is correct
12 Correct 668 ms 241704 KB Output is correct
13 Correct 200 ms 230392 KB Output is correct
14 Correct 377 ms 239836 KB Output is correct
15 Correct 260 ms 231772 KB Output is correct
16 Correct 709 ms 241024 KB Output is correct
17 Correct 661 ms 240968 KB Output is correct
18 Correct 649 ms 240632 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 230488 KB Output is correct
2 Correct 204 ms 230520 KB Output is correct
3 Correct 202 ms 230512 KB Output is correct
4 Correct 209 ms 230876 KB Output is correct
5 Correct 242 ms 230884 KB Output is correct
6 Correct 215 ms 230996 KB Output is correct
7 Correct 201 ms 230392 KB Output is correct
8 Correct 379 ms 239552 KB Output is correct
9 Correct 376 ms 235744 KB Output is correct
10 Correct 1106 ms 240680 KB Output is correct
11 Correct 685 ms 241016 KB Output is correct
12 Correct 661 ms 241272 KB Output is correct
13 Correct 202 ms 230520 KB Output is correct
14 Correct 375 ms 239628 KB Output is correct
15 Correct 229 ms 231976 KB Output is correct
16 Correct 691 ms 240880 KB Output is correct
17 Correct 649 ms 240692 KB Output is correct
18 Correct 653 ms 240724 KB Output is correct
19 Runtime error 1584 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -