Submission #469420

#	Time	Username	Problem	Language	Result	Execution time	Memory
469420		flashmt	Sails (IOI07_sails)	C++17	100 / 100	132 ms	4404 KiB

sails

#include <bits/stdc++.h>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
const int N = 100100;

int n, H, f[N * 4], mn[N * 4];
vector<pair<int, int>> a;
long long re;

int Get_Value(int nd,int l,int r,int x)
{
	if (l==r) return f[nd];
	int m=(l+r)>>1;
	if (x<=m) return f[nd]+Get_Value(nd<<1,l,m,x);
	return f[nd]+Get_Value((nd<<1)+1,m+1,r,x);
}

int Find_First_Position(int nd,int l,int r,int x,int y,int v)
{
	int m=(l+r)>>1,res=0;
	if (l==x && r==y)
	{
		if (mn[nd]>v) return 0;
		if (l==r) return l;
		if (mn[nd<<1]+f[nd]<=v) return Find_First_Position(nd<<1,l,m,l,m,v-f[nd]);
		return Find_First_Position((nd<<1)+1,m+1,r,m+1,r,v-f[nd]);
	}
	if (x<=m) res=Find_First_Position(nd<<1,l,m,x,min(y,m),v-f[nd]);
	if (res) return res;
	if (m<y) res=Find_First_Position((nd<<1)+1,m+1,r,max(x,m+1),y,v-f[nd]);
	return res;
}

void Add(int nd,int l,int r,int x,int y)
{
	if (l==x && r==y) f[nd]++, mn[nd]++;
	else
	{
		int m=(l+r)>>1;
		if (x<=m) Add(nd<<1,l,m,x,min(y,m));
		if (m<y)
		{
			Add((nd<<1)+1,m+1,r,max(x,m+1),y);
			mn[nd]=mn[(nd<<1)+1]+f[nd];
		}
	}
}

void Calc_Result(int nd,int l,int r)
{
	if (l==r) re+=1LL*f[nd]*(f[nd]-1)>>1;
	else
	{
		int m=(l+r)>>1;
		f[nd<<1]+=f[nd];
		f[(nd<<1)+1]+=f[nd];
		Calc_Result(nd<<1,l,m);
		Calc_Result((nd<<1)+1,m+1,r);
	}
}

int main()
{
	int i,h,k,v,l,r;
	cin >> n;
	fr(i,1,n)
	{
		scanf("%d%d",&h,&k);
		H=max(H,h);
		a.push_back(make_pair(h,k));
	}
	sort(a.begin(),a.end());
	fr(i,0,n-1)
	{
		h=a[i].first; k=a[i].second;
		v=Get_Value(1,1,H,h-k+1);
		r=Find_First_Position(1,1,H,1,h,v-1);
		if (!r) r=h+1;
		else Add(1,1,H,r,h);
		k-=(h-r+1);
		l=Find_First_Position(1,1,H,1,r-1,v);
		Add(1,1,H,l,l+k-1);
	}
	Calc_Result(1,1,H);
	cout << re << endl;
	return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&h,&k);
      |   ~~~~~^~~~~~~~~~~~~~

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