제출 #1357436

#제출 시각아이디문제언어결과실행 시간메모리
1357436NAMINSails (IOI07_sails)C++20
100 / 100
152 ms2224 KiB
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

const int mxN = 100005;

struct STsum{
	int len=1;
	vector<int> tree;
	STsum(int l){
		while(len<l)
			len*=2;
		tree=vector<int>(2*len,0);
	}
	
	void update(int idx,int v){
		idx += len;
		tree[idx]+=v;
		for(idx/=2;idx>=1;idx/=2)
			tree[idx]=tree[idx*2]+tree[idx*2+1];
	}

	void range_update(int l,int r,int v){
		update(l,v);
		update(r+1,-v);
	}

	int query(int idx){
		int l=1,r=idx;
		int res = 0;
		l+=len,r+=len;
		while(l<=r){
			if(l%2==1)
				res += tree[l++];
			if(r%2==0)
				res += tree[r--];
			l/=2,r/=2;
		}
		return res;
	}

	int lb(int v){
		int idx = len;
		int lo=1,hi=len-1;
		while(lo<=hi){
			int mid = lo+(hi-lo)/2;
			if(query(mid)<=v){
				idx=mid;
				hi=mid-1;
			}
			else
				lo=mid+1;
		}
		return idx;
	}
};

void solve(){
	int N;
	cin >> N;
	vector<pair<int,int>> event(N);//h,k
	for(int i=0;i<N;i++){
		cin >> event[i].first >> event[i].second;
	}
	sort(event.begin(),event.end());
	STsum seg(mxN+5);
	for(auto [h,k] : event){
		int x = seg.query(h-k+1);
		int l = seg.lb(x),r=min(seg.lb(x-1),h+1)-1;
		int extra = max(0,k-(h-r));
		if(extra>0){
			seg.range_update(l,l+extra-1,1);
			seg.range_update(r+1,h,1);
		}
		else{
			seg.range_update(h-k+1,h,1);
		}

	}
	ll ans = 0;
	for(int i=1;i<mxN;i++){
		int v = seg.query(i);
		ans+=1LL*(v-1)*v/2;
	}
	cout << ans << endl;
}

int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…