Submission #1295980

#TimeUsernameProblemLanguageResultExecution timeMemory
1295980Jawad_Akbar_JJSails (IOI07_sails)C++20
60 / 100
88 ms3556 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = (1<<17) + 1;
int Mn[N<<1], Mx[N<<1], num[N<<1];

void Add(int i, int v, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		num[cur] += v;
		if (num[cur] == 0)
			Mn[cur] = N, Mx[cur] = 0;
		else
			Mn[cur] = Mx[cur] = st;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Add(i, v, lc, st, mid);
	Add(i, v, rc, mid, en);
	Mn[cur] = min(Mn[lc], Mn[rc]);
	Mx[cur] = max(Mx[lc], Mx[rc]);
}

int get1(int k, int cur = 1, int st = 1, int en = N){
	if (en - st == 1)
		return st;
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (Mn[rc] <= k)
		return get1(k, rc, mid, en);
	return get1(k, lc, st, mid);
}

int get2(int k, int cur = 1, int st = 1, int en = N){
	if (en - st == 1)
		return st;
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (Mx[lc] >= k)
		return get2(k, lc, st, mid);
	return get2(k, rc, mid, en);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	for (int i=1;i<(N<<1);i++)
		Mn[i] = N;

	int n;
	cin>>n;

	vector<pair<int,int>> vec;
	for (int i=1;i<=n;i++){
		int h, k;
		cin>>h>>k;

		vec.push_back({h, k});
	}
	sort(vec.begin(), vec.end());

	Add(1, -1);
	Add(N - 2, -1);
	for (auto [h, k] : vec){
		int f = get1(h - k + 1);
		int s = get2(h - k + 1) - 1;

		int l1 = h - min(h, s);
		// cout<<h<<" "<<k<<" "<<l1<<" "<<f<<" "<<s<<endl;
		Add(s + 1, 1); Add(s + l1 + 1, -1);
		Add(f, 1), Add(f + k - l1, -1);
	}

	Add(1, 1);

	long long Ans = 0;
	for (int i=1, sm = 0;i<=n;i++){
		sm += num[131071 + i];
		// cout<<sm<<'\n';
		Ans += (1LL * sm * (sm - 1)) / 2;
	}
	cout<<Ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...