oj.uz

Submission #500738

# Submission time Handle Problem Language Result Execution time Memory
500738 2022-01-01T04:38:31 Z Eyed Sails (IOI07_sails) C++17
100 / 100
 648 ms 6176 KB 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9 + 7;

ll n;
pii arr[100005];

bool mark[400030];
ll lazy[400030];
ll t[400030];

//range sum queries, range add updates

void push(ll v, ll tl, ll tr) {
	if (mark[v]) {
		mark[v] = false;
		lazy[2 * v] += lazy[v];
		lazy[2 * v + 1] += lazy[v];
		ll mid = (tl + tr) / 2;
		t[2 * v] += (mid - tl + 1) * lazy[v];
		t[2 * v + 1] += (tr - mid) * lazy[v];
		lazy[v] = 0;
		mark[2 * v] = true;
		mark[2 * v + 1] = true;
	}
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll x) {
	if (l > r) return;
	if (l <= tl && r >= tr) {
		mark[v] = true;
		lazy[v] += x;
		t[v] += (tr - tl + 1) * x;
		return;
	}
	push(v, tl, tr);
	ll mid = (tl + tr) / 2;
	update(2 * v, tl, mid, max(tl, l), min(mid, r), x);
	update(2 * v + 1, mid + 1, tr, max(mid + 1, l), min(tr, r), x);
	t[v] = t[2 * v] + t[2 * v + 1];
} void update(ll l, ll r, ll x) { update(1, 0, 100005, l, r, x); }
ll query(ll v, ll tl, ll tr, ll l, ll r) {
	if (l > r) return 0;
	if (l <= tl && r >= tr) return t[v];
	push(v, tl, tr);
	ll mid = (tl + tr) / 2;
	return query(2 * v, tl, mid, max(l, tl), min(r, mid)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), min(tr, r));
} ll query(ll l, ll r) { return query(1, 0, 100005, l, r); }
ll get(ll r) { return query(r, r); }

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (ll i = 0; i < n; ++i) cin >> arr[i].first >> arr[i].second;
	sort(arr, arr + n);
	ll sum2 = 0;
	ll maxH = 0;
	for (ll i = 0; i < n; ++i) {
		ll h = arr[i].first;
		ll k = arr[i].second;
		sum2 += k;
		maxH = max(maxH, h);
		ll key = get(h - k);
		ll l = 0;
		ll r = h - k;
		while (l < r) {
			ll mid = (l + r) / 2;
			if (get(mid) != key) l = mid + 1;
			else r = mid;
		}
		ll lb = l;
		l = h - k;
		r = h - 1;
		while (l < r) {
			ll mid = (l + r + 1) / 2;
			if (get(mid) != key) r = mid - 1;
			else l = mid;
		}
		ll rb = l;
		update(rb + 1, h - 1, 1);
		update(lb, lb + (rb - (h - k)), 1);
	}
	ll sum = 0;
	for (ll i = 0; i < maxH; ++i) {
		sum += (query(i, i) * query(i, i));
	}
	//cout << sum << " " << sum2 << endl;
	cout << (sum - sum2) / 2 << endl;
	

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 640 KB Output is correct
2 Correct 30 ms 4668 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1840 KB Output is correct
2 Correct 115 ms 1216 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 2100 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 3444 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 5752 KB Output is correct
2 Correct 443 ms 5844 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 6084 KB Output is correct
2 Correct 255 ms 5308 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 6176 KB Output is correct
2 Correct 419 ms 3192 KB Output is correct