Submission #500738

#	Time	Username	Problem	Language	Result	Execution time	Memory
500738		Eyed	Sails (IOI07_sails)	C++17	100 / 100	648 ms	6176 KiB

sails

#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 / 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