oj.uz

Submission #123565

# Submission time Handle Problem Language Result Execution time Memory
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;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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