oj.uz

Submission #896000

# Submission time Handle Problem Language Result Execution time Memory
896000 2023-12-31T12:00:49 Z jhon06 Wall (IOI14_wall) C++14
0 / 100
 3000 ms 11520 KB 
#include "wall.h"
#include<bits/stdc++.h>
#define ll long long
#define maxl 1e18
#define minl -(1e18)
#define f first
#define lb lower_bound
#define ub upper_bound
#define bg begin()
#define nd end()
#define rnd(x) random_shuffle((x).begin, (x).end())
#define reverse(x) reverse((x).begin(), (x).end())
#define del erase
#define ssub substr
#define tp tuple
#define pp pop_back
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define vi vector<ll>
#define vii vector<pair<ll,ll>>
#define lsb(x) (x&(-x))
#define log2(i) (__builtin_clzll(1) - __builtin_clzll(i))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((a*b)/gdc(a,b))
#define dbg(x) (cerr<<"["<<"R"<<":"<<__LINE__<<"]"<<#x<<" -> "<<(x)<<'\n',(x))
#define rand (rand() * (RAND_MAX + 1) + rand()) % (int)1e6
#define count(x) __builtin_popcount(x)
//nth elemtnh
const int fx[]={+1,0,-1,+0};
const int fy[]={+0,-1,0,+1};
//cout << setprecision(10) << fixed << sol << '\n'; se voglio specificare precisione
//lower_bound(arr,arr+a,valore); unique() remove dups fill(vec,number) merge() binary_search()
// per hashing polinomiale scelgo numero primo simile a tutti i caratteri che posso mettere
using namespace std;
struct Node{
	ll mini;
	ll mas;
	ll nodes;
	ll val;
	Node():mini(maxl),mas(-1),val(-1) {	};
	void set(ll n){
		mini=maxl;
		mas=-1;
		nodes=1;
		val=0;
	}
	void merge(Node a,Node b){
		nodes=a.nodes+b.nodes;
	}
};
struct segTree{
	vector<Node> seg;
	ll sz;
	void propagate(ll p){
		if(seg[p].nodes==1)return;
		if(seg[p].mini!=maxl){
		    propagate(p*2);
		    propagate(p*2+1);
			seg[p*2].mini=min(seg[p*2].mini,seg[p].mini);
			seg[p*2+1].mini=min(seg[p*2+1].mini,seg[p].mini);
			seg[p*2].mas=min(seg[p*2].mas,seg[p].mini);
			seg[p*2+1].mas=min(seg[p*2+1].mas,seg[p].mini);
			seg[p].mini=maxl;
		}
		if(seg[p].mas!=-1){
			propagate(p*2);
			propagate(p*2+1);
			seg[p*2].mini=maxl;
			seg[p*2+1].mini=maxl;
			seg[p*2].mas=max(seg[p*2].mas,seg[p].mas);
			seg[p*2+1].mas=max(seg[p*2+1].mas,seg[p].mas);
			seg[p].mas=-1;
		}
	}
	void make(int n){
		sz=n;
		seg.resize(n*4);
	}
	void set(ll pos,ll value){
		set2(pos,value,1,0,sz-1);
	}
	void set2(int pos,ll value,ll p,int l,int r){
	//	propagate(p);
		if(l==r){
			seg[p].set(value);
		}
		else{
			ll mid=(r-l)/2+l;
			if(pos<=mid){
				set2(pos,value,p*2,l,mid);
			}
			else{
				set2(pos,value,p*2+1,mid+1,r);
			}
			seg[p].merge(seg[p*2],seg[p*2+1]);
		}
	}
	ll get(int l,int r){ //indici l,r compresi 0 based
		return get2(l,r,1,0,sz-1);
	}
	ll get2(int l,int r,ll p,int tl,int tr){
		if(r<tl || l>tr)return 0;
		propagate(p);
		if(l==tl && r==tr){
			return max((ll)0,min(seg[p].mas,seg[p].mini));
		}
		else{
			ll mid=(tr-tl)/2+tl;
			if(l>mid){
				return get2(l,r,p*2+1,mid+1,tr);
			}
			else{
				return get2(l,r,p*2,tl,mid);
			}
		}
	}
	void lz_mini(int l,int r,ll v){
		lz_mini2(l,r,1,0,sz-1,v);
	}
	void lz_mini2(int l,int r,ll p,int tl,int tr,ll v){
		if(r<tl || l>tr)return;
		propagate(p);
		if(tl>=l && tr<=r){
			seg[p].mini=min(seg[p].mini,v);
			seg[p].mas=min(seg[p].mas,v);
		}
		else{
			ll mid=(tr-tl)/2+tl;
			lz_mini2(l,r,p*2,tl,mid,v);
			lz_mini2(l,r,p*2+1,mid+1,tr,v);
			seg[p].merge(seg[p*2],seg[p*2+1]);
		}
	}
	
	void lz_masi(int l,int r,ll v){
		lz_masi2(l,r,1,0,sz-1,v);
	}
	void lz_masi2(int l,int r,ll p,int tl,int tr,ll v){
	/*	dbg(tl);
		dbg(tr);*/
		if(r<tl || l>tr)return;
		propagate(p);
		if(tl>=l && tr<=r){
			seg[p].mas=v;
			seg[p].mini=maxl;
		}
		else{
			ll mid=(tr-tl)/2+tl;
			lz_masi2(l,r,p*2,tl,mid,v);
			lz_masi2(l,r,p*2+1,mid+1,tr,v);
			seg[p].merge(seg[p*2],seg[p*2+1]);
		}
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	segTree si;
	si.make(n);
	for(int i=0;i<n;i++)si.set(i,0);
	for(int i=0;i<k;i++){
		if(op[i]==1){
			si.lz_masi(left[i],right[i],height[i]);
		}
		else{
			si.lz_mini(left[i],right[i],height[i]);
		}
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=max((ll)0,si.get(i,i));
	}
    return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 3 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 101 ms 11520 KB Output is correct
3 Execution timed out 3033 ms 8308 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Incorrect 3 ms 528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 3 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -