Submission #1039551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039551		pcc	Measures (CEOI22_measures)	C++17	100 / 100	343 ms	50628 KiB

Main

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 2e14;
const ll mxn = 3e5+10;

struct node{
	ll mx,mn,tag;
	node(){
		mx = -inf,mn = inf<<1,tag = 0;
	}
};

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	node seg[mxn*4];
	node pull(node tl,node tr){
		node re;
		re.mx = max(tl.mx+tl.tag,tr.mx+tr.tag);
		re.mn = min(tl.mn+tl.tag,tr.mn+tr.tag);
		return re;
	}
	void push(int now,int l,int r){
		seg[ls].tag += seg[now].tag;
		seg[rs].tag += seg[now].tag;
		seg[now].tag = 0;
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	void modify(int now,int l,int r,int s,int e,ll v){
		if(l>=s&&e>=r){
			seg[now].tag += v;
			return;
		}
		push(now,l,r);
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	void setval(int now,int l,int r,int p,ll v){
		if(l == r){
			seg[now].mx = seg[now].mn = v;
			seg[now].tag = 0;
			return;
		}
		push(now,l,r);
		if(mid>=p)setval(ls,l,mid,p,v);
		else setval(rs,mid+1,r,p,v);
		seg[now] = pull(seg[ls],seg[rs]);
	}
	ll getmx(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r){
			return seg[now].mx+seg[now].tag;
		}
		push(now,l,r);
		if(mid>=e)return getmx(ls,l,mid,s,e);
		else if(mid<s)return getmx(rs,mid+1,r,s,e);
		else return max(getmx(ls,l,mid,s,e),getmx(rs,mid+1,r,s,e));
	}
	ll getmn(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r){
			return seg[now].mn+seg[now].tag;
		}
		push(now,l,r);
		if(mid>=e)return getmn(ls,l,mid,s,e);
		else if(mid<s)return getmn(rs,mid+1,r,s,e);
		else return min(getmn(ls,l,mid,s,e),getmn(rs,mid+1,r,s,e));
	}
	SEG(){}
#undef ls
#undef rs
#undef mid
};

SEG seg;
ordered_set<int> st;
vector<ll> all;
int ids[mxn];
ll N,M,D;
ll ans;
ll arr[mxn];
ll req[mxn];

ll bis(ll x,ll y){
	ll l = ans,r = 3e15;
	while(l != r){
		ll mid = (l+r)>>1;
		if(x<=y+mid*2)r = mid;
		else l = mid+1;
	}
	return l;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(ids,-1,sizeof(ids));
	cin>>N>>M>>D;
	D<<=1;
	for(int i = 0;i<N+M;i++){
		cin>>arr[i];
		arr[i]<<=1;
		all.push_back(arr[i]);
	}

	{
		sort(all.begin(),all.end());
		for(int i = 0;i<N+M;i++){
			auto pos = lower_bound(all.begin(),all.end(),arr[i])-all.begin();
			if(ids[pos] == -1)arr[i] = ids[pos] = pos;
			else arr[i] = ids[pos];
			ids[pos]++;
		}
	}

	for(int i = 0;i<N+M;i++){
		int pos = arr[i];
		seg.modify(0,0,N+M,pos,N+M,-D);
		ll sh = st.order_of_key(pos);
		seg.setval(0,0,N+M,pos,all[pos]-D*sh);
		ll x = seg.getmx(0,0,N+M,0,pos);
		ll y = seg.getmn(0,0,N+M,pos,N+M);
		ans = bis(x,y);
		req[i] = ans;
		st.insert(pos);
	}
	for(int i = N;i<N+M;i++)cout<<(req[i]>>1)<<(req[i]&1?".5 ":" ");
	cout<<'\n';
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41