oj.uz

Submission #246966

# Submission time Handle Problem Language Result Execution time Memory
246966 2020-07-10T16:45:44 Z Evirir Wall (IOI14_wall) C++17
61 / 100
 992 ms 262144 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(6*size_, Node{0,INF});
		lazy.resize(6*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);
			}
			if(lazy[k].mx != INF)
			{
				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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 15 ms 3584 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 13 ms 3712 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 182 ms 9388 KB Output is correct
3 Correct 274 ms 11128 KB Output is correct
4 Correct 866 ms 34296 KB Output is correct
5 Correct 314 ms 34040 KB Output is correct
6 Correct 311 ms 34296 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 15 ms 3584 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 181 ms 9336 KB Output is correct
9 Correct 277 ms 11000 KB Output is correct
10 Correct 932 ms 34168 KB Output is correct
11 Correct 325 ms 34168 KB Output is correct
12 Correct 317 ms 34448 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 184 ms 9336 KB Output is correct
15 Correct 59 ms 7552 KB Output is correct
16 Correct 977 ms 34220 KB Output is correct
17 Correct 336 ms 34168 KB Output is correct
18 Correct 320 ms 34296 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 16 ms 3584 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 177 ms 9336 KB Output is correct
9 Correct 281 ms 11000 KB Output is correct
10 Correct 893 ms 34168 KB Output is correct
11 Correct 326 ms 34204 KB Output is correct
12 Correct 406 ms 34424 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 181 ms 9336 KB Output is correct
15 Correct 57 ms 7544 KB Output is correct
16 Correct 992 ms 34144 KB Output is correct
17 Correct 325 ms 34040 KB Output is correct
18 Correct 403 ms 34264 KB Output is correct
19 Runtime error 332 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -