Submission #1249249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249249		1ncogn1to	Sails (IOI07_sails)	C++20	90 / 100	45 ms	2632 KiB

sails

#include <bits/stdc++.h>
using namespace std;
struct stree
{
	vector<int>tree;
	int N; 
	stree(int n){
		N=1;
		while(N<n)
			N*=2;
		tree.resize(N*3);
		N--;
	}
	int query(int x)
	{
		return tree[x+N+N+1];
	}
	void add(int x, int val)
	{
		x+=N+N+1;
		tree[x]+=val;
		if(tree[x]!=0)
			tree[x-N-1]=1;
		else
			tree[x-N-1]=0;
		x-=N;
		x--;
		x/=2;
		while(x)
		{
			tree[x]=tree[x*2]+tree[x*2+1];
			x/=2;
		}
	}
	int first_right(int v, int tl, int tr, int l, int r)
	{
		if(l>r||tree[v]==0)
			return -1;
		if(tl==tr)
			return tl;
		int tm=(tl+tr)/2;
		int res=-1;
		if(l<=tm)
			res=first_right(v*2,tl,tm,l,min(r,tm));
		if(res==-1&&r>tm)
			res=first_right(v*2+1,tm+1,tr,max(l,tm+1),r);
		return res;
	}
	int first_right(int x)
	{
		return first_right(1,1,N+1,x,N+1);
	}
	int first_left(int v, int tl, int tr, int l, int r)
	{
		if(l>r||tree[v]==0)
			return -1;
		if(tl==tr)
			return tl;
		int tm=(tl+tr)/2;
		int res=-1;
		if(r>tm)
			res=first_left(v*2+1,tm+1,tr,max(l,tm+1),r);
		if(res==-1&&l<=tm)
			res=first_left(v*2,tl,tm,l,min(r,tm));
		return res;
	}
	int first_left(int x)
	{
		return first_left(1,1,N+1,1,x);
	}
};
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<pair<int,int>>hk(n);
	for(int i=0; i<n; i++)
		cin>>hk[i].first>>hk[i].second;
	sort(hk.begin(),hk.end());
	stree tr(hk[hk.size()-1].first+1);
	int h,k;
	for(int i=0; i<n; i++)
	{
		h=hk[i].first;
		k=hk[i].second;
		int a,b;
		if(tr.query(h-k+1)!=0)
			a=h-k+1;
		else
		{
			a=tr.first_right(h-k+1);
			int hml=k-(h+1-a);
			if(a==-1)
				a=h+1,hml=k;
			b=tr.first_left(h-k+1);
			if(b==-1)
				b=1;
			tr.add(b,1);
			tr.add(b+hml,-1);
		}
		tr.add(a,1);
		tr.add(h+1,-1);
	}
	int sm=0;
	long long int res=0;
	for(int i=1; i<=h; i++)
	{
		sm+=tr.query(i);
		res+=(sm*(sm-1)/2);
	}
	cout<<res<<"\n";
}

• 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: 0 / 10
• Subtask 11: 10 / 10