oj.uz

Submission #246945

# Submission time Handle Problem Language Result Execution time Memory
246945 2020-07-10T15:49:37 Z Evirir Wall (IOI14_wall) C++17
0 / 100
 234 ms 13920 KB 
#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

bool DEBUG = 1;
const int MAXN = 2000005;

class LazySegmentTree{
private:
	int size_;
	vector<ll> v;
	vector<ii> lazy;
	
	void update1(int s, int e, ll val, int k, int l, int r){
		push(k, l, r);
		if(r < s || e < l) return;
		if(s <= l && r <= e){
			lazy[k] = ii(0,val);
			push(k, l, r);
		}
		else{
			update1(s, e, val, k*2, l, (l+r)>>1);
			update1(s, e, val, k*2+1, ((l+r)>>1)+1, r);
			v[k] = merge(v[k*2], v[k*2+1]);
		}
	}
	
	void update2(int s, int e, ll val, int k, int l, int r){
		push(k, l, r);
		if(r < s || e < l) return;
		if(s <= l && r <= e){
			lazy[k] = ii(1,val);
			push(k, l, r);
		}
		else{
			update2(s, e, val, k*2, l, (l+r)>>1);
			update2(s, e, val, k*2+1, ((l+r)>>1)+1, r);
			v[k] = merge(v[k*2], v[k*2+1]);
		}
	}
	
	ll query(int s, int e, int k, int l, int r){
		push(k, l, r);
		if(r < s || e < l) return 0; //dummy value
		if(s <= l && r <= e) return v[k];
		ll lc = query(s, e, k*2, l, (l+r)>>1);
		ll rc = query(s, e, k*2+1, ((l+r)>>1)+1, r);
		return merge(lc, rc);
	}
 
public:
	LazySegmentTree(): v(vector<ll>()), lazy(vector<ii>()) {}
	LazySegmentTree(int n){
		for(size_=1;size_<n;) size_<<=1;
		v.resize(size_*4);
		lazy.resize(size_*4,ii(-1,-1));
	}
	void reset(){
		v.assign(size_*4,0);
		lazy.assign(size_*4,ii(-1,-1));
	}
	inline void push(int k, int l, int r){
		if(lazy[k].F!=-1){
			if(!lazy[k].F){
				v[k]=max(v[k], lazy[k].S);
			}
			else{
				v[k]=min(v[k], lazy[k].S);
			}
			
			if(l!=r){
				lazy[k*2]=lazy[k];
				lazy[k*2+1]=lazy[k];
			}
			lazy[k]=ii(-1,-1);
		}
	}
	inline ll merge(ll x, ll y){
		return x+y;
	}
	inline void update1(int l, int r, ll val){
		update1(l, r, val, 1, 0, size_-1);
	}
	inline void update2(int l, int r, ll val){
		update2(l, r, val, 1, 0, size_-1);
	}
	inline ll query(int l, int r){
		return query(l, r, 1, 0, size_-1);
	}
};

void buildWall(int n, int K, int op[], int L[], int R[], int H[], int ans[])
{
	LazySegmentTree st(n);
	
	for(int z=0;z<K;z++)
	{
		if(op[z]==1) st.update1(L[z],R[z],H[z]);
		else st.update2(L[z],R[z],H[z]);
	}
	
	for(int i=0;i<n;i++){
		ans[i]=st.query(i,i);
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Incorrect 8 ms 416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 177 ms 13920 KB Output is correct
3 Incorrect 234 ms 10492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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