제출 #123565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123565		vex	Sails (IOI07_sails)	C++14	5 / 100	34 ms	3064 KiB

sails

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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