提出 #52091252

---

ソースコード 拡げる

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

#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
ii arr[200005];
int ans[200005];

int idx[200005];
int pos[200005];

set<int> s;
int l[200005],r[200005];

int sum=0;
int curr=0;
int ss=0;

void add(int i){
	auto it=s.insert(i).fi;
	
	int a=*prev(it);
	int b=*next(it);
	
	l[i]=a;
	r[i]=b;
	r[a]=l[b]=i;
	
	if (i<curr){
		ss++;
		sum+=arr[idx[i]].fi;
	}
}

void del(int i){
	auto it=s.find(i);
	
	if (i<=curr){
		ss--;
		sum-=arr[idx[i]].fi;
	}
	if (i==curr){
		curr=l[curr];
	}
	
	int a=*prev(it);
	int b=*next(it);
	
	r[a]=b;
	l[b]=a;
	
	s.erase(it);
}

void rebal(int k){
	while (ss<k && r[curr]!=200004){
		curr=r[curr];
		ss++;
		sum+=arr[idx[curr]].fi;
	}
	while (ss>k){
		ss--;
		sum-=arr[idx[curr]].fi;
		curr=l[curr];
	}
}

void dnc(int l,int r,int kl,int kr){
	int km=kl+kr>>1;
	
	int best=1e18;
	int idx=-1;
	rep(x,l,r+1){
		rebal(km-1);
		if (ss==km-1){
			if (best>sum+arr[x].fi+arr[x].se){
				best=sum+arr[x].fi+arr[x].se;
				idx=x;
			}
		}
		add(pos[x]);
	}
	
	//cout<<l<<" "<<r<<" "<<kl<<" "<<kr<<" "<<idx<<" "<<km<<endl;
	
	ans[km]=best;
	
	rep(x,r+1,idx) del(pos[x]);
	if (km!=kr) dnc(idx,r,km+1,kr);
	
	rep(x,idx,l) del(pos[x]);
	if (km!=kl) dnc(l,idx,kl,km-1);
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	s={0,200004};
	r[0]=200004;
	l[200004]=0;
	
	cin>>n;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	rep(x,1,n+1) arr[x].fi=-arr[x].fi;
	
	sort(arr+1,arr+n+1,[](ii i,ii j){
		return i.se<j.se;
	});
	
	rep(x,1,n+1) idx[x]=x;
	sort(idx+1,idx+n+1,[](int i,int j){
		return arr[i]<arr[j];
	});
	
	rep(x,1,n+1) pos[idx[x]]=x;
	
	dnc(1,n,1,n);
	
	rep(x,1,n+1) cout<<-ans[x]<<endl;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘void dnc(long long int, long long int, long long int, long long int)’:
Main.cpp:90:18: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   90 |         int km=kl+kr>>1;
      |                ~~^~~

ジャッジ結果