Submission #649486

#	Time	Username	Problem	Language	Result	Execution time	Memory
649486		ymm	Sails (IOI07_sails)	C++17	100 / 100	737 ms	2620 KiB

sails

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'032;
int cnt[N];
pii mast[N];
int n;

__attribute__((optimize("O3,unroll-loops"),target("avx")))
void add(int l, int r)
{
	Loop (i,l,r)
		cnt[i]++;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> mast[i].first >> mast[i].second;
	sort(mast, mast + n);
	Loop (i,0,n) {
		int x = cnt[mast[i].first - mast[i].second];
		int l = lower_bound(cnt, cnt + mast[i].first, x, greater()) - cnt;
		int r = upper_bound(cnt, cnt + mast[i].first, x, greater()) - cnt;
		add(r, mast[i].first);
		add(l, l + mast[i].second - (mast[i].first - r));
	}
	ll ans = 0;
	Loop (i,0,N)
		ans += (ll)cnt[i] * (cnt[i]-1) / 2;
	cout << ans << '\n';
}

• 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