oj.uz

Submission #246963

# Submission time Handle Problem Language Result Execution time Memory
246963 2020-07-10T16:43:05 Z Evirir Wall (IOI14_wall) C++17
61 / 100
 1008 ms 262148 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);
			}
			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 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 15 ms 2560 KB Output is correct
5 Correct 12 ms 2560 KB Output is correct
6 Correct 12 ms 2560 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 185 ms 8440 KB Output is correct
3 Correct 278 ms 8056 KB Output is correct
4 Correct 858 ms 34808 KB Output is correct
5 Correct 361 ms 35192 KB Output is correct
6 Correct 314 ms 33656 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 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 14 ms 2560 KB Output is correct
5 Correct 12 ms 2560 KB Output is correct
6 Correct 12 ms 2560 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 185 ms 13944 KB Output is correct
9 Correct 301 ms 11572 KB Output is correct
10 Correct 927 ms 34784 KB Output is correct
11 Correct 324 ms 35168 KB Output is correct
12 Correct 323 ms 33784 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 184 ms 13948 KB Output is correct
15 Correct 60 ms 5504 KB Output is correct
16 Correct 1008 ms 34552 KB Output is correct
17 Correct 334 ms 34044 KB Output is correct
18 Correct 318 ms 34044 KB Output is correct

Subtask #4
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 2560 KB Output is correct
5 Correct 12 ms 2560 KB Output is correct
6 Correct 11 ms 2560 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 179 ms 13944 KB Output is correct
9 Correct 286 ms 11488 KB Output is correct
10 Correct 842 ms 34680 KB Output is correct
11 Correct 320 ms 35192 KB Output is correct
12 Correct 320 ms 33656 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 190 ms 13924 KB Output is correct
15 Correct 56 ms 5504 KB Output is correct
16 Correct 981 ms 34680 KB Output is correct
17 Correct 336 ms 34108 KB Output is correct
18 Correct 330 ms 34040 KB Output is correct
19 Runtime error 371 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -