Submission #103384

#	Time	Username	Problem	Language	Result	Execution time	Memory
103384		Berted	Sails (IOI07_sails)	C++14	100 / 100	105 ms	3200 KiB

sails

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define pll pair<ll,ll>
#define mkp make_pair
#define fst first
#define snd second
#define pub push_back
using namespace std;
class FenwickTree
{
	private:
		vector<ll> ft;
		void as(int x,ll v)
		{
			for (;x<ft.size();x+=(x&(-x))) {ft[x]+=v;}
		}
	public:	
		FenwickTree(int n)
		{
			ft.assign(n+4,0);
		}
		ll rq(int x)
		{
			ll to = 0;
			//cout<<x<<" ";
			for (;x;x-=(x&(-x))) {to+=ft[x];}
			//cout<<to<<"\n";
			return to;
		}
		void qsg(int l,int r)
		{
			if (l>r) {return;}
			as(l,1);as(r+1,-1);
		}
};
pll ar[100001]={};FenwickTree dt(100000);
int bsr(int l,int r,ll v)
{
	int pv;
	while (l<r)
	{
		pv = (l+r)>>1;
		if (dt.rq(pv)>=v) {l=pv+1;}
		else {r=pv;}
	}
	return l;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>ar[i].fst>>ar[i].snd;
	}
	sort(ar,ar+n);
	for (int i=0;i<n;i++)
	{
		ll vl = dt.rq(ar[i].fst-ar[i].snd+1),idx1 = bsr(1,ar[i].fst+1,vl),idx2 = bsr(1,ar[i].fst+1,vl+1),tk;
		tk=max((ll)0,ar[i].fst-idx1+1);
		dt.qsg(idx1,ar[i].fst);
		dt.qsg(idx2,idx2+ar[i].snd-tk-1);
		//cout<<vl<<" "<<idx1<<" "<<ar[i].fst<<" "<<idx2<<" "<<idx2+ar[i].snd-tk-1<<"\n";
	}
	ll rs = 0,tp;
	for (int i=1;i<=100000;i++)
	{
		tp = dt.rq(i);
		rs += (tp*(tp-1))/2;
	}
	cout<<rs<<"\n";
	return 0;
}

Compilation message (stderr)

sails.cpp: In member function 'void FenwickTree::as(int, long long int)':
sails.cpp:17:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (;x<ft.size();x+=(x&(-x))) {ft[x]+=v;}
          ~^~~~~~~~~~

• 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