oj.uz

Submission #343447

# Submission time Handle Problem Language Result Execution time Memory
343447 2021-01-03T23:54:55 Z sofapuden Sails (IOI07_sails) C++14
25 / 100
 78 ms 4616 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3820 KB Output is correct
2 Correct 21 ms 3820 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3820 KB Output is correct
2 Correct 21 ms 3820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3820 KB Output is correct
2 Correct 21 ms 3916 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 4076 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 4204 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 4460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 4616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 4588 KB Output isn't correct
2 Halted 0 ms 0 KB -