답안 #123565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123565 2019-07-01T15:45:43 Z vex Sails (IOI07_sails) C++14
5 / 100
34 ms 3064 KB
#include <bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define vis first
#define br second
using namespace std;

int n;
pii a[maxn];
long long zb[maxn];


void update(int l,int r)
{
	zb[l]++;
	zb[r+1]--;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int maxx=1;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].vis>>a[i].br;
		maxx=max(maxx,a[i].vis);
	}
	
	sort(a,a+n);
	
	for(int i=1;i<=maxx;i++)zb[i]=0LL;
	int tre=maxx;
	for(int i=n-1;i>=0;i--)
	{
		tre=min(tre,a[i].vis);
		if(tre>=a[i].br)
		{
			update(tre-a[i].br+1,tre);
			tre-=a[i].br;
			if(tre==0)tre=a[i].vis;
		}
		else
		{
			update(1,tre);
			int ost=a[i].br-tre;
			tre=a[i].vis;
			
			update(tre-ost+1,tre);
			tre-=ost;
			if(tre==0)tre=a[i].vis;
		}
	}
	
	long long sol=zb[1]*(zb[1]-1)/2;
	for(int i=2;i<=maxx;i++)
	{
		zb[i]+=zb[i-1];
		sol+=zb[i]*(zb[i]-1)/2;
	}
	
	//for(int i=1;i<=maxx;i++)cout<<zb[i]<<" ";cout<<endl;
	
	cout<<sol<<endl;
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 1144 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 1656 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 2524 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -