oj.uz

Submission #810982

# Submission time Handle Problem Language Result Execution time Memory
810982 2023-08-06T18:53:47 Z arashMLG Wall (IOI14_wall) C++17
100 / 100
 451 ms 107104 KB 
#include "wall.h"
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

//https://quera.org/profile/4dykhk

typedef long long     ll;
typedef long double   ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N =2e6 + 23;
const int mod = 1e9+7; // 998244353
const int LOG = 23;
const ll inf = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define F           first
#define S           second
#define pb          push_back
#define ms(x,y)     memset((x) , (y) , sizeof (x))
#define done        return cout<<endl , 0;
#define kill(x)     cout<<x<<endl, exit(0);
#define isIn(x,s,e) ((x) >= (s) && (x) <= e)
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define pc(x)       __builtin_popcount(x)
#define ctz(x)      __builtin_ctz(x)
#define MinHeap(x)  priority_queue<x, vector<x> , greater<x> >
#define MaxHeap(x)  priority_queue<x, vector<x>>
#define lc          (v << 1)
#define rc          ((v<<1) |1)
//#define int      ll

ll pw(ll a, ll b, ll md = mod){ll res = 1; while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int ans[N];
pii t[N<<2];

void upd(int v,int l,int r,int x,int op,int tl,int tr) {
	if(l > r) return;
	x = max(x,t[v].F);
	x= min(x,t[v].S);
	if(l == tl && r == tr-1) {
		 if(op)
		 	t[v].S = x;
		 else
		 	t[v].F = x;
		 return;
	}
	
	int mid=(tl+tr)/2;
	
	upd(lc,l,min(mid-1,r),x,op,tl,mid);
	upd(rc,max(l,mid),r,x,op,mid,tr);
}


void make(int v,int x,int tl,int tr) {
	x = max(x,t[v].F);
	x = min(x,t[v].S);
	if(tr- tl == 1) {
		ans[tl] = x;
		return;
	}
	int mid=(tl+tr)/2;
	
	make(lc,x,tl,mid);	
	make(rc,x,mid,tr);
}


void buildWall(int n, int k, int op[], int left[], int right[], int h[], int finalHeight[]){
	for(int i = 0 ; i< (N<<2); i ++) t[i] = {0,mod};
	for(int i = k-1; i >=0 ; i--) upd(1,left[i],right[i],h[i],op[i] -1,0,n);
	make(1,0,0,n);
	for(int i = 0 ; i< n ; i++) finalHeight[i] = ans[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62920 KB Output is correct
2 Correct 26 ms 62924 KB Output is correct
3 Correct 26 ms 62964 KB Output is correct
4 Correct 28 ms 63156 KB Output is correct
5 Correct 27 ms 63116 KB Output is correct
6 Correct 28 ms 63152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62884 KB Output is correct
2 Correct 123 ms 70732 KB Output is correct
3 Correct 129 ms 70204 KB Output is correct
4 Correct 297 ms 81348 KB Output is correct
5 Correct 208 ms 82384 KB Output is correct
6 Correct 198 ms 80792 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62796 KB Output is correct
2 Correct 24 ms 62932 KB Output is correct
3 Correct 24 ms 62948 KB Output is correct
4 Correct 27 ms 63140 KB Output is correct
5 Correct 27 ms 63188 KB Output is correct
6 Correct 28 ms 63200 KB Output is correct
7 Correct 25 ms 62868 KB Output is correct
8 Correct 123 ms 76508 KB Output is correct
9 Correct 128 ms 70280 KB Output is correct
10 Correct 297 ms 81356 KB Output is correct
11 Correct 205 ms 82320 KB Output is correct
12 Correct 204 ms 80884 KB Output is correct
13 Correct 23 ms 62900 KB Output is correct
14 Correct 125 ms 76536 KB Output is correct
15 Correct 39 ms 64096 KB Output is correct
16 Correct 305 ms 81528 KB Output is correct
17 Correct 201 ms 80980 KB Output is correct
18 Correct 201 ms 80924 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62932 KB Output is correct
2 Correct 23 ms 63000 KB Output is correct
3 Correct 24 ms 62876 KB Output is correct
4 Correct 26 ms 63132 KB Output is correct
5 Correct 27 ms 63196 KB Output is correct
6 Correct 27 ms 63188 KB Output is correct
7 Correct 24 ms 62932 KB Output is correct
8 Correct 125 ms 76492 KB Output is correct
9 Correct 127 ms 70148 KB Output is correct
10 Correct 296 ms 81348 KB Output is correct
11 Correct 224 ms 82356 KB Output is correct
12 Correct 197 ms 80716 KB Output is correct
13 Correct 24 ms 62856 KB Output is correct
14 Correct 129 ms 76748 KB Output is correct
15 Correct 41 ms 64148 KB Output is correct
16 Correct 299 ms 81520 KB Output is correct
17 Correct 204 ms 80972 KB Output is correct
18 Correct 208 ms 80976 KB Output is correct
19 Correct 419 ms 107104 KB Output is correct
20 Correct 417 ms 104632 KB Output is correct
21 Correct 430 ms 107084 KB Output is correct
22 Correct 429 ms 104548 KB Output is correct
23 Correct 419 ms 104656 KB Output is correct
24 Correct 420 ms 104540 KB Output is correct
25 Correct 426 ms 104612 KB Output is correct
26 Correct 429 ms 107056 KB Output is correct
27 Correct 451 ms 107036 KB Output is correct
28 Correct 421 ms 104592 KB Output is correct
29 Correct 420 ms 104576 KB Output is correct
30 Correct 421 ms 104580 KB Output is correct