Submission #343447

#	Time	Username	Problem	Language	Result	Execution time	Memory
343447		sofapuden	Sails (IOI07_sails)	C++14	25 / 100	78 ms	4616 KiB

sails

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> seg(4e5+5,0);

void add(int l, int r, int p, int lb, int rb){
	if(l > rb || r < lb)return;
	if(l >= lb && r <= rb){
		seg[p]++;
		return;
	}
	int mid = (l+r)>>1;
	add(l,mid,p<<1,lb,rb);
	add(mid+1,r,(p<<1)+1,lb,rb);
}

ll ch(int l, int r, int p, int x){
	if(l > x || r < x)return 0;
	if(l == x && r == x)return seg[p];
	int mid = (l+r)>>1;
	return seg[p]+ch(l,mid,p<<1,x)+ch(mid+1,r,(p<<1)+1,x);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n; cin >> n;
	vector<array<int,2>> v(n);
	for(auto &x : v)cin >> x[0] >> x[1];
	for(int i = 0; i < n; ++i){
		add(0,100000,1,v[i][0]-v[i][1]+1,v[i][0]);
	}
	vector<int> am(100001);
	for(int i = 0; i < 100001; ++i){
		am[i] = ch(0,100000,1,i);
	}
	int l = 1, r = 100000;
	ll bes = LONG_LONG_MAX;
	while(l <= r){
		ll cu1 = 0;
		int mid = (l+r)>>1;
		ll res = 0;
		for(int i = 100000; i >= 1; --i){
			if(res+am[i] >= mid){
				res -= (mid-am[i]);
				cu1+=((mid)*(mid-1))/2;
			}
			else{
				cu1+=((am[i]+res)*(am[i]+res-1))/2;
				res = 0;
			}
		}
		if(res){
			cu1-=((mid)*(mid-1)/2);
			cu1+=((mid+res)*(mid+res-1))/2;
			bes = min(bes,cu1);
		}
		else{
			bes = min(bes,cu1);
		}
		ll cu2 = 0;
		mid--;
		res = 0;
		for(int i = 100000; i >= 1; --i){
			if(res+am[i] >= mid){
				res -= (mid-am[i]);
				cu2+=((mid)*(mid-1))/2;
			}
			else{
				cu2+=((am[i]+res)*(am[i]+res-1))/2;
				res = 0;
			}
		}
		if(res){
			cu2-=((mid)*(mid-1)/2);
			cu2+=((mid+res)*(mid+res-1))/2;
			bes = min(bes,cu2);
		}
		else{
			bes = min(bes,cu2);
		}
		if(cu1 >= cu2){
			r = mid-1;
		}
		else{
			l = mid+2;
		}
	}
	cout << bes << "\n";			
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10