oj.uz

Submission #142633

# Submission time Handle Problem Language Result Execution time Memory
142633 2019-08-10T07:09:00 Z Berted Sails (IOI07_sails) C++14
100 / 100
 110 ms 3832 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1220 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1400 KB Output is correct
2 Correct 25 ms 1912 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1912 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2552 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3320 KB Output is correct
2 Correct 73 ms 3196 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3576 KB Output is correct
2 Correct 64 ms 3320 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3832 KB Output is correct
2 Correct 64 ms 3676 KB Output is correct