oj.uz

Submission #500736

# Submission time Handle Problem Language Result Execution time Memory
500736 2022-01-01T04:07:37 Z Eyed Sails (IOI07_sails) C++17
0 / 100
 98 ms 7292 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); }

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 counter = 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 nextCnt = counter + (k - 1);
		if (nextCnt < h) update(counter, nextCnt, 1);
		else {
			update(counter, h - 1, 1);
			update(0, (nextCnt % h), 1);
		}
		counter = ((nextCnt+1) % h);
	}
	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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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