oj.uz

Submission #649486

# Submission time Handle Problem Language Result Execution time Memory
649486 2022-10-10T09:47:14 Z ymm Sails (IOI07_sails) C++17
100 / 100
 737 ms 2620 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 540 KB Output is correct
2 Correct 20 ms 868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1052 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1324 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 2152 KB Output is correct
2 Correct 303 ms 2128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 2408 KB Output is correct
2 Correct 26 ms 1996 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 2620 KB Output is correct
2 Correct 50 ms 2236 KB Output is correct