oj.uz

Submission #526898

# Submission time Handle Problem Language Result Execution time Memory
526898 2022-02-16T14:56:30 Z SAAD Wall (IOI14_wall) C++17
100 / 100
 1673 ms 96540 KB 
#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
pair<int,int> seg[10000000] ;
int L , R , nn ;
bool segth[10000000] ;
int final[5000000] ;
struct act {
	string type ;
	int h ;
	pair<int,int> range ;
};
int sth ( int idx , int l , int r , pair<int,int> mnx , int ans ){
    if ( idx > (nn*2)+1 || segth[idx] ) return 0;
    if ( l >= L && r <= R ) segth[idx] = true;
    //cout << "hi " << idx << " " << ans << " " << endl; 
    if ( l > R || r < L ) return 0;

    if ( mnx.F == ans ) {
    	if ( seg[idx].F >= mnx.F ) {
    		mnx = { seg[idx].F , 1000000 } ;
    		ans = seg[idx].F ;
		}
		else {
			if ( mnx.F >= seg[idx].S ) {
				mnx = { 0 , seg[idx].S } ;
    			ans = seg[idx].S ;
			}
		}
		
    }
    else if ( mnx.S == ans ) {
    	if ( seg[idx].S <= mnx.S ) {
    		mnx = { 0 , seg[idx].S } ;
    		ans = seg[idx].S ;
    	}
    	else {
    		if ( mnx.S <= seg[idx].F ) {
    			mnx = { seg[idx].F , 1000000 } ;
    			ans = seg[idx].F ;
    		}
    	}
    }
    if ( idx > nn ) {
    	//cout << ans << " " << idx-nn-1 << endl << endl;
    	final[idx-nn-1] = ans ;
    	return 0;
    }
    sth(idx*2,l,(l+r)/2,mnx,ans);
	sth(idx*2+1,(l+r)/2+1,r,mnx,ans);
	return 0;
}
int segment(int idx , int l , int r , pair<int,int> mnx ){
	if ( idx > (nn*2+1) || segth[idx] ) return 0;
	if ( l > R || r < L ) return 0;
		pair <int,int> best ;
		best = {max(mnx.F,seg[idx].F),min(mnx.S,seg[idx].S)} ;
		if ( best == seg[idx] ) return 0;
		if (mnx.F >= seg[idx].S ) {
		    if ( l == r ) {
		        final[idx-nn-1] = seg[idx].S ;
		        segth[idx] = true;
		    }
			sth(idx*2,l,(l+r)/2,{0,seg[idx].S},seg[idx].S);
			sth(idx*2+1,(l+r)/2+1,r,{0,seg[idx].S},seg[idx].S);
		}
		else if ( mnx.S <= seg[idx].F ) {
		    if ( l == r ) {
		        final[idx-nn-1] = seg[idx].F ;
		        segth[idx] = true;
		    }
			sth(idx*2,l,(l+r)/2,{seg[idx].F,1000000},seg[idx].F);
			sth(idx*2+1,(l+r)/2+1,r,{seg[idx].F,1000000},seg[idx].F);
		}
		
		if (!(l >= L && r <= R)) {
			segment(idx*2  ,l,(l+r)/2,best);
			segment(idx*2+1,(l+r)/2+1,r,best);
		} else seg[idx] = best ;
	return 0;
}
void buildWall(int n, int k, int op[], int left[] , int right[],int height[], int finalHeight[]){
	queue <act> q ;
	act a ;
	for ( int i = k-1 ; i >= 0 ; i-- ) {
		a.type = (op[i]==1?"min":"max") ;
		a.h = height[i] ;
		a.range = {left[i],right[i]} ;
		q.push(a);
	}
	a.type = "max" ;
	a.h = 0 ;
	nn = log2(n);
	if (pow(2,nn) != n) nn++;
	nn = pow(2,nn)-1 ;
	a.range = {0,nn} ;
	q.push(a);
	for ( int i = (nn*2)+1 ; i >= 1 ; i-- ) seg[i] = {0,1000000} ;
	while ( !q.empty() ) {
		L = q.front().range.F ;
		R = q.front().range.S ;
		pair<int,int> b ;
		if ( q.front().type == "min" ) b = {q.front().h,1000000} ;
		else b = {0,q.front().h} ;
		segment(1,0,nn,b);
		q.pop();
	}
	for ( int i = 0 ; i < n ; i++ ) {
		finalHeight[i] = final[i] ;
		//cout << final[i] << " " ;
	}
}
/*int main(){
   ios_base::sync_with_stdio(0);cin.tie(0);
   int n , k ;
   vi op , l , r , h , f ;
   op = { 1 , 2 , 1 , 2 } ;
   l = {0,0,0,0} ;
   r = {0,0,1,1} ;
   h = {3,4,1,5} ;
   f = {0,0,0,0} ;
   n = 2 ;
   k = 4 ;
   
   buildWall(n,k,op,l,r,h,f);
   return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 4 ms 1100 KB Output is correct
5 Correct 5 ms 1100 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 155 ms 38568 KB Output is correct
3 Correct 81 ms 18260 KB Output is correct
4 Correct 210 ms 45608 KB Output is correct
5 Correct 279 ms 46200 KB Output is correct
6 Correct 641 ms 44524 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 5 ms 1100 KB Output is correct
6 Correct 5 ms 1084 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 158 ms 38624 KB Output is correct
9 Correct 82 ms 18236 KB Output is correct
10 Correct 204 ms 45660 KB Output is correct
11 Correct 288 ms 46200 KB Output is correct
12 Correct 644 ms 44520 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 160 ms 38632 KB Output is correct
15 Correct 15 ms 3560 KB Output is correct
16 Correct 201 ms 45548 KB Output is correct
17 Correct 570 ms 45048 KB Output is correct
18 Correct 574 ms 44952 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 4 ms 1084 KB Output is correct
5 Correct 5 ms 1080 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 161 ms 38760 KB Output is correct
9 Correct 81 ms 18316 KB Output is correct
10 Correct 203 ms 45568 KB Output is correct
11 Correct 287 ms 46124 KB Output is correct
12 Correct 644 ms 44512 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 162 ms 38604 KB Output is correct
15 Correct 15 ms 3660 KB Output is correct
16 Correct 205 ms 45688 KB Output is correct
17 Correct 582 ms 45020 KB Output is correct
18 Correct 567 ms 44972 KB Output is correct
19 Correct 1655 ms 96140 KB Output is correct
20 Correct 1639 ms 96244 KB Output is correct
21 Correct 1641 ms 96216 KB Output is correct
22 Correct 1645 ms 96540 KB Output is correct
23 Correct 1640 ms 96248 KB Output is correct
24 Correct 1659 ms 96348 KB Output is correct
25 Correct 1653 ms 96212 KB Output is correct
26 Correct 1645 ms 96380 KB Output is correct
27 Correct 1673 ms 96200 KB Output is correct
28 Correct 1657 ms 96300 KB Output is correct
29 Correct 1656 ms 96236 KB Output is correct
30 Correct 1653 ms 96240 KB Output is correct