oj.uz

Submission #708318

# Submission time Handle Problem Language Result Execution time Memory
708318 2023-03-11T14:51:34 Z mars4 Wall (IOI14_wall) C++17
100 / 100
 1125 ms 214364 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <wall.h>

using namespace std;
using namespace __gnu_pbds; 

#define ff              first
#define ss              second
#define ll              int64_t
#define ld              long double
#define nl              cout<<"\n"
#define i128            __int128_t
#define all(v)          v.begin(),v.end()
#define mset(a,v)       memset((a),(v),sizeof(a))
#define forn(i,a,b)     for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b)     for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define mod         1'000'000'007
#define mod2        998'244'353 
#define inf         1'000'000'000'000'007
#define pi          3.14159265358979323846

template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;

template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)        {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                 {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                   {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class T> ostream& operator<<(ostream& out,ordered_set<T> &s)           {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)         {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail> 
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

//---------------------------------mars4---------------------------------

class Segtree
{
	ll N;
	vector<ll> segtree;
	vector<ll> minval;
	vector<ll> maxval;

	void _set_maxval(ll i)
	{
		if(maxval[i]<minval[i])
		{
			maxval[i]=minval[i];
		}
	}

	void _set_minval(ll i)
	{
		if(minval[i]>maxval[i])
		{
			minval[i]=maxval[i];
		}
	}

	void _setval(ll i,ll val)
	{
		if(val>0)
		{
			minval[i]=max(minval[i],val);
			_set_maxval(i);
		}
		else
		{
			maxval[i]=min(maxval[i],-val);
			_set_minval(i);
		}
	}

	void _push_maxval(ll st,ll ed,ll val,ll i)
	{
		if(st^ed)
		{
			maxval[i<<1]=min(maxval[i<<1],val);
			_set_minval(i<<1);
			maxval[i<<1|1]=min(maxval[i<<1|1],val);
			_set_minval(i<<1|1);
		}
	}

	void _push_minval(ll st,ll ed,ll val,ll i)
	{
		if(st^ed)
		{
			minval[i<<1]=max(minval[i<<1],val);
			_set_maxval(i<<1);
			minval[i<<1|1]=max(minval[i<<1|1],val);
			_set_maxval(i<<1|1);
		}
	}

	void _update(ll st,ll ed,ll l,ll h,ll val,ll i=1)
	{
		if(maxval[i]!=inf)
		{
			segtree[i]=min(segtree[i],maxval[i]);
			_push_maxval(st,ed,maxval[i],i);
			maxval[i]=inf;
		}
		if(minval[i])
		{
			segtree[i]=max(segtree[i],minval[i]);
			_push_minval(st,ed,minval[i],i);
			minval[i]=0;
		}
		if(st>ed or st>h or ed<l)
			return;
		if(st>=l and ed<=h)
		{
			_setval(i,val);
			if(maxval[i]!=inf)
			{
				segtree[i]=min(segtree[i],maxval[i]);
				_push_maxval(st,ed,maxval[i],i);
				maxval[i]=inf;
			}
			if(minval[i])
			{
				segtree[i]=max(segtree[i],minval[i]);
				_push_minval(st,ed,minval[i],i);
				minval[i]=0;
			}
			return;
		}
		ll mid=(st+ed)>>1;
		_update(st,mid,l,h,val,i<<1);
		_update(mid+1,ed,l,h,val,i<<1|1);
	}

	ll _query(ll st,ll ed,ll l,ll r,ll i=1)
	{
		if(maxval[i]!=inf)
		{
			segtree[i]=min(segtree[i],maxval[i]);
			_push_maxval(st,ed,maxval[i],i);
			maxval[i]=inf;
		}
		if(minval[i])
		{
			segtree[i]=max(segtree[i],minval[i]);
			_push_minval(st,ed,minval[i],i);
			minval[i]=0;
		}
		if(st>ed or st>r or ed<l)
			return 0;
		if(st>=l and ed<=r)
			return segtree[i];
		ll mid=(st+ed)>>1;
		return _query(st,mid,l,r,i<<1)+_query(mid+1,ed,l,r,i<<1|1);
	}

	public:
	void init(ll n)
	{
		N=n;
		segtree=vector<ll>(N<<2);
		minval=vector<ll>(N<<2);
		maxval=vector<ll>(N<<2,inf);
	}

	void update(ll l,ll r,ll val)
	{
		_update(0,N-1,l,r,val);
	}

	ll query(ll l,ll r)
	{
		return _query(0,N-1,l,r);
	}
};

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	Segtree s;
	s.init(n);
	forn(i,0,k)
	{
		if(op[i]==1)
		{
			s.update(left[i],right[i],height[i]);
		}
		else
		{
			s.update(left[i],right[i],-height[i]);
		}
	}
	forn(i,0,n)
	{
		finalHeight[i]=s.query(i,i);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 12 ms 1364 KB Output is correct
5 Correct 7 ms 1336 KB Output is correct
6 Correct 8 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 142 ms 8112 KB Output is correct
3 Correct 225 ms 5324 KB Output is correct
4 Correct 568 ms 27468 KB Output is correct
5 Correct 304 ms 27996 KB Output is correct
6 Correct 310 ms 26528 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 1492 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 7 ms 1364 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 138 ms 13884 KB Output is correct
9 Correct 178 ms 9016 KB Output is correct
10 Correct 549 ms 27548 KB Output is correct
11 Correct 271 ms 28092 KB Output is correct
12 Correct 328 ms 26416 KB Output is correct
13 Correct 1 ms 284 KB Output is correct
14 Correct 143 ms 13920 KB Output is correct
15 Correct 44 ms 2988 KB Output is correct
16 Correct 860 ms 27540 KB Output is correct
17 Correct 267 ms 26896 KB Output is correct
18 Correct 265 ms 26968 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1364 KB Output is correct
5 Correct 6 ms 1364 KB Output is correct
6 Correct 6 ms 1332 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 129 ms 13828 KB Output is correct
9 Correct 176 ms 9120 KB Output is correct
10 Correct 550 ms 27612 KB Output is correct
11 Correct 253 ms 28108 KB Output is correct
12 Correct 257 ms 26600 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 132 ms 13880 KB Output is correct
15 Correct 43 ms 3000 KB Output is correct
16 Correct 865 ms 27536 KB Output is correct
17 Correct 265 ms 26956 KB Output is correct
18 Correct 275 ms 26896 KB Output is correct
19 Correct 1060 ms 214284 KB Output is correct
20 Correct 1092 ms 214348 KB Output is correct
21 Correct 1100 ms 214280 KB Output is correct
22 Correct 1066 ms 214244 KB Output is correct
23 Correct 1102 ms 214364 KB Output is correct
24 Correct 1075 ms 214280 KB Output is correct
25 Correct 1125 ms 214316 KB Output is correct
26 Correct 1074 ms 214224 KB Output is correct
27 Correct 1041 ms 214232 KB Output is correct
28 Correct 1045 ms 214280 KB Output is correct
29 Correct 1077 ms 214272 KB Output is correct
30 Correct 1040 ms 214276 KB Output is correct