oj.uz

Submission #198611

# Submission time Handle Problem Language Result Execution time Memory
198611 2020-01-26T23:05:08 Z MetB Sails (IOI07_sails) C++14
5 / 100
 294 ms 34808 KB 
#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);
		assert (l != -1);
		assert (r != -1);
		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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31608 KB Output is correct
2 Correct 19 ms 31608 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 31608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 31608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 31608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 31736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 32248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 32636 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 33236 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 34428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 34696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 34808 KB Output isn't correct
2 Halted 0 ms 0 KB -