oj.uz

Submission #810979

# Submission time Handle Problem Language Result Execution time Memory
810979 2023-08-06T18:50:41 Z arashMLG Wall (IOI14_wall) C++17
0 / 100
 139 ms 76500 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 = 0 ; i< k ; 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Incorrect 26 ms 62980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62884 KB Output is correct
2 Incorrect 139 ms 76500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62824 KB Output is correct
2 Incorrect 25 ms 63068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62828 KB Output is correct
2 Incorrect 26 ms 62956 KB Output isn't correct
3 Halted 0 ms 0 KB -