Submission #198610

#	Time	Username	Problem	Language	Result	Execution time	Memory
198610		MetB	Sails (IOI07_sails)	C++14	5 / 100	295 ms	34808 KiB

sails

#include <bits/stdc++.h>
 
#define N 1000001
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

struct V {
	ll min, max, midl, midr;
	V () {
		min = max = midl = midr = INF;
	}

	V (ll x) {
		min = max = midl = midr = x;
	}

	V (ll a, ll b, ll c, ll d) : min (a), max (b), 
		midl (c), midr (d) {}
};

struct LazySeg {
	V t[N];
	ll ta[N], start;
	V merge (V a, V b) {
		return V (a.min, b.max, a.max, b.min);
	}

	void push (ll node) {
		t[node].min += ta[node];
		t[node].max += ta[node];
		t[node].midl += ta[node];
		t[node].midr += ta[node];
		if (node < start) {
			ta[2 * node] += ta[node];
			ta[2 * node + 1] += ta[node];
		}
		ta[node] = 0;
	}

	void build (ll n) {
		start = 1;
		while (start < n) start <<= 1;

		for (ll i = 0; i < n; i++)
			t[start + i] = V (0);

		for (ll i = start - 1; i > 0; i--)
			t[i] = merge (t[2 * i], t[2 * i + 1]);
	}

	void update (ll node, ll tl, ll tr, ll l, ll r, ll d) {
		push (node);
		if (r < tl || tr < l) return;
		if (l <= tl && tr <= r) {
			ta[node] += d;
			push (node);
			return;
		}

		ll tm = (tl + tr) / 2;
		update (2 * node, tl, tm, l, r, d);
		update (2 * node + 1, tm + 1, tr, l, r, d);
		t[node] = merge (t[2 * node], t[2 * node + 1]);
	}

	ll get (ll node, ll tl, ll tr, ll x) {
		push (node);
		if (tl == tr) return t[node].min;
		ll tm = (tl + tr) / 2;
		if (x <= tm) return get (2 * node, tl, tm, x);
		else return get (2 * node + 1, tm + 1, tr, x);
	}

	ll lower_bound (ll node, ll tl, ll tr, ll n, ll x) {
		push (node);
		if (n <= tl) return -1;
		if (tr < n) {
			if (t[node].min > x) return -1;
			while (node < start) {
				push (node);
				if (t[node].midr > x) node *= 2;
				else node = 2 * node + 1;
			}
			return node - start;
		}

		int tm = (tl + tr) / 2;
		int r = lower_bound (2 * node + 1, tm + 1, tr, n, x);
		if (r != -1) return r;
		else return lower_bound (2 * node, tl, tm, n, x);
	}

	ll upper_bound (ll node, ll tl, ll tr, ll n, ll x) {
		push (node);
		if (n <= tl) return -1;
		if (tr < n) {
			if (t[node].max < x) return -1;
			while (node < start) {
				push (node);
				if (t[node].midl < x) node = 2 * node + 1;
				else node *= 2;
			}
			return node - start;
		}

		int tm = (tl + tr) / 2;
		int l = upper_bound (2 * node, tl, tm, n, x);
		if (l != -1) return l;
		else return upper_bound (2 * node + 1, tm + 1, tr, n, x);
	}
} t;

ll n, m;
pair <ll, ll> a[N];

int main () {
	cin >> n;

	for (ll i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		m = max (m, a[i].first);
	}
	t.build (m);

	sort (a, a + n);

	for (ll i = n - 1; i >= 0; i--) {
		if (!a[i].second) continue;
		ll x = t.get (1, 0, t.start - 1, a[i].second - 1);
		ll l = t.upper_bound (1, 0, t.start - 1, a[i].first, x);
		ll r = t.lower_bound (1, 0, t.start - 1, a[i].first, x);
		if (l) t.update (1, 0, t.start - 1, 0, l - 1, 1);
		a[i].second -= l;
		t.update (1, 0, t.start - 1, r - a[i].second + 1, r, 1);
	}

	ll sum = 0;

	for (ll i = 0; i < m; i++) {
		ll x = t.get (1, 0, t.start - 1, i);
		sum += x * (x - 1) / 2;
	}

	cout << sum;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10