oj.uz

Submission #246967

# Submission time Handle Problem Language Result Execution time Memory
246967 2020-07-10T16:46:49 Z Evirir Wall (IOI14_wall) C++17
100 / 100
 1483 ms 223736 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(3*size_, Node{0,INF});
		lazy.resize(3*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 5 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 16 ms 2048 KB Output is correct
5 Correct 17 ms 2048 KB Output is correct
6 Correct 12 ms 2048 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 181 ms 8312 KB Output is correct
3 Correct 271 ms 6904 KB Output is correct
4 Correct 952 ms 20948 KB Output is correct
5 Correct 323 ms 21000 KB Output is correct
6 Correct 316 ms 21112 KB Output is correct

Subtask #3
29.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 Correct 7 ms 384 KB Output is correct
4 Correct 15 ms 2048 KB Output is correct
5 Correct 12 ms 2048 KB Output is correct
6 Correct 11 ms 2048 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 189 ms 8348 KB Output is correct
9 Correct 282 ms 6904 KB Output is correct
10 Correct 847 ms 21240 KB Output is correct
11 Correct 319 ms 21044 KB Output is correct
12 Correct 317 ms 21048 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 179 ms 8312 KB Output is correct
15 Correct 55 ms 4096 KB Output is correct
16 Correct 954 ms 21108 KB Output is correct
17 Correct 326 ms 20984 KB Output is correct
18 Correct 315 ms 20984 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 15 ms 2048 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 11 ms 2048 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 194 ms 8412 KB Output is correct
9 Correct 282 ms 6864 KB Output is correct
10 Correct 865 ms 21240 KB Output is correct
11 Correct 313 ms 20984 KB Output is correct
12 Correct 317 ms 21112 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 177 ms 8460 KB Output is correct
15 Correct 55 ms 4216 KB Output is correct
16 Correct 965 ms 21060 KB Output is correct
17 Correct 317 ms 20984 KB Output is correct
18 Correct 318 ms 21132 KB Output is correct
19 Correct 1246 ms 223468 KB Output is correct
20 Correct 1227 ms 223440 KB Output is correct
21 Correct 1279 ms 223456 KB Output is correct
22 Correct 1264 ms 223416 KB Output is correct
23 Correct 1179 ms 223392 KB Output is correct
24 Correct 1187 ms 223736 KB Output is correct
25 Correct 1205 ms 223608 KB Output is correct
26 Correct 1483 ms 223452 KB Output is correct
27 Correct 1204 ms 223480 KB Output is correct
28 Correct 1184 ms 223608 KB Output is correct
29 Correct 1206 ms 223656 KB Output is correct
30 Correct 1224 ms 223480 KB Output is correct