oj.uz

Submission #246955

# Submission time Handle Problem Language Result Execution time Memory
246955 2020-07-10T16:25:18 Z Evirir Wall (IOI14_wall) C++17
0 / 100
 301 ms 8316 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;

struct Node {
	ll mn = 0, mx = INF;
};

class LazySegmentTree {
private:
	vector<Node> v, lazy;
	int size_;
	
	void update(int s, int e, const Node &val, int k, int l, int r)
	{
		push(k, l, r);
		if(r < s || e < l) return;
		if(s <= l && r <= e){
			lazy[k] = val;
			push(k, l, r);
			return;
		}
		
		int mid = (l+r)>>1;
		update(s, e, val, 2*k, l, mid);
		update(s, e, val, 2*k+1, mid+1, r);
	}
	
	Node query(int s, int e, int k, int l, int r)
	{
		push(k, l, r);
		if(r < s || e < l) return Node{-1,INF}; //dummy value
		if(s <= l && r <= e) return v[k];
		
		int mid = (l+r)/2;
		Node lc = query(s, e, 2*k, l, mid);
		Node rc = query(s, e, 2*k+1, mid+1, r);
		return merge(lc, rc);
	}

public:
	LazySegmentTree(): v(vector<Node>()), lazy(vector<Node>()){}
	LazySegmentTree(int n_){
		for(size_=1;size_<n_;) size_<<=1;
		v.resize(4*size_, Node{0,INF});
		lazy.resize(4*size_, Node{-1,INF});
	}
	
	void push(int k, int l, int r){
		if(lazy[k].mn != -1 || lazy[k].mx != INF){
			if(lazy[k].mn != -1){
				amax(v[k].mn, lazy[k].mn);
				amax(v[k].mx, lazy[k].mn);
			}
			else
			{
				amin(v[k].mn, lazy[k].mx);
				amin(v[k].mx, lazy[k].mx);
			}
			
			if(l!=r){
				mergelazy(lazy[k*2],lazy[k]);
				mergelazy(lazy[k*2+1],lazy[k]);
			}
			lazy[k] = Node{-1,INF};
		}
	}
	
	inline Node merge(const Node &a, const Node &b){
		return Node{(a.mn != -1 ? a.mn : b.mn), (a.mx != INF ? a.mx : b.mx)};
	}
	
	inline void mergelazy(Node &a, const Node &b){
		amax(a.mn, b.mn);
		amax(a.mx, b.mn);
		amin(a.mn, b.mx);
		amin(a.mx, b.mx);
	}
	
	inline void update(int s, int e, const Node &val){
		update(s, e, val, 1, 0, size_-1);
	}
	
	inline Node query(int s, int e){
		return query(s, e, 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 i=0;i<K;i++)
	{
		if(op[i]==1) st.update(L[i],R[i],Node{H[i],INF});
		else st.update(L[i],R[i],Node{-1,H[i]});
	}
	
	forn(i,0,n) ans[i] = st.query(i,i).mn;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Incorrect 6 ms 384 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 181 ms 8316 KB Output is correct
3 Incorrect 301 ms 7800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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