oj.uz

답안 #103383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103383 2019-03-30T05:48:04 Z Berted Sails (IOI07_sails) C++14
60 / 100
 150 ms 3904 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,int 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()
{
	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<=n;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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 1280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 1912 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 2424 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 3236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 150 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 3904 KB Output is correct
2 Correct 100 ms 3760 KB Output is correct