oj.uz

Submission #1065116

# Submission time Handle Problem Language Result Execution time Memory
1065116 2024-08-18T23:07:55 Z Edu175 Wall (IOI14_wall) C++17
100 / 100
 878 ms 120420 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto kjfg:v)cout<<kjfg<<" ";cout<<"\n";}
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
const ll INF=1e5+5;
typedef ll tn; // node type
typedef ii tl; // lazy type
// tn unit(ll v){return v;}
#define NEUT 0
tl CLEAR={-1,INF}; // cleared lazy node
tn oper(tn a, tn b){
	return max(a,b);
}
void acum(tl &a, tl v){ // accumulate lazy node
	auto [l,r]=a;
	auto [l2,r2]=v;
	if(l2>=r)a={l2,l2};
	else if(r2<=l)a={r2,r2};
	else a={max(l,l2),min(r,r2)};
}
tn calc(ll s, ll e, tn a, tl v){ // calculate STree range, a=previous value
	a=max(a,v.fst);
	a=min(a,v.snd);
	return a;
} 
struct STree{
	vector<tn>st; vector<tl>lazy; ll n;
	STree(ll n):st(4*n+5,NEUT),lazy(4*n+5,CLEAR),n(n){}
	void push(ll k, ll s, ll e){
		if(lazy[k]==CLEAR)return;
		st[k]=calc(s,e,st[k],lazy[k]);
		if(e-s!=1){
			acum(lazy[2*k],lazy[k]);
			acum(lazy[2*k+1],lazy[k]);
		}
		lazy[k]=CLEAR;
	}
	void upd(ll k, ll s, ll e, ll a, ll b, tl v){ // range update
		push(k,s,e);
		if(e<=a||b<=s)return;
		if(a<=s&&e<=b){
			acum(lazy[k],v);
			push(k,s,e);
			return;
		}
		ll m=(s+e)/2;
		upd(2*k,s,m,a,b,v),upd(2*k+1,m,e,a,b,v);
		st[k]=oper(st[2*k],st[2*k+1]);
	}
	tn query(ll k, ll s, ll e, ll a, ll b){
		if(e<=a||b<=s)return NEUT;
		push(k,s,e);
		if(a<=s&&e<=b)return st[k];
		ll m=(s+e)/2;
		return oper(query(2*k,s,m,a,b),query(2*k+1,m,e,a,b));
	}
	void upd(ll a, ll b, tl v){upd(1,0,n,a,b,v);}
	tn query(ll a, ll b){return query(1,0,n,a,b);}
};
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ret[]){
	STree st(n);
	fore(i,0,q){
		r[i]++,op[i]--;
		tl v;
		if(op[i]==0)v={h[i],INF};
		else v={-1,h[i]};
		st.upd(l[i],r[i],v);
	}
	// fore(i,0,q){
	// 	fore(j,l[i],r[i]){
	// 		if(op[i]==1)a[j]=max(a[j],h[i]);
	// 		else a[j]=min(a[j],h[i]);
	// 	}
	// }
	fore(i,0,n)ret[i]=st.query(i,i+1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 14004 KB Output is correct
3 Correct 162 ms 8284 KB Output is correct
4 Correct 510 ms 22868 KB Output is correct
5 Correct 206 ms 23336 KB Output is correct
6 Correct 213 ms 21716 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 7 ms 1112 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 82 ms 13908 KB Output is correct
9 Correct 161 ms 8372 KB Output is correct
10 Correct 491 ms 22708 KB Output is correct
11 Correct 212 ms 23376 KB Output is correct
12 Correct 208 ms 21940 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 83 ms 13948 KB Output is correct
15 Correct 33 ms 2140 KB Output is correct
16 Correct 608 ms 22868 KB Output is correct
17 Correct 221 ms 22200 KB Output is correct
18 Correct 214 ms 22352 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 944 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 13916 KB Output is correct
9 Correct 162 ms 8360 KB Output is correct
10 Correct 488 ms 22864 KB Output is correct
11 Correct 205 ms 23380 KB Output is correct
12 Correct 207 ms 21844 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 83 ms 13820 KB Output is correct
15 Correct 33 ms 2136 KB Output is correct
16 Correct 620 ms 22868 KB Output is correct
17 Correct 216 ms 22356 KB Output is correct
18 Correct 216 ms 22228 KB Output is correct
19 Correct 834 ms 120400 KB Output is correct
20 Correct 798 ms 120396 KB Output is correct
21 Correct 812 ms 120420 KB Output is correct
22 Correct 817 ms 120400 KB Output is correct
23 Correct 801 ms 120404 KB Output is correct
24 Correct 810 ms 120400 KB Output is correct
25 Correct 865 ms 120336 KB Output is correct
26 Correct 827 ms 120400 KB Output is correct
27 Correct 834 ms 120400 KB Output is correct
28 Correct 817 ms 120376 KB Output is correct
29 Correct 808 ms 120404 KB Output is correct
30 Correct 878 ms 120400 KB Output is correct