oj.uz

Submission #583147

# Submission time Handle Problem Language Result Execution time Memory
583147 2022-06-24T22:25:22 Z Shreyan_Paliwal Sails (IOI07_sails) C++17
100 / 100
 251 ms 3840 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000;
const int segn = (1<<18);
const int maxh = 100000;

int n;

pair<int,int> masts[maxn];

int seg[segn];
int flg[segn];

void push(int p, int l, int r) {
	if (l == r) {flg[p] = 0; return;}
	if (flg[p] == 0) return;
	seg[2*p] += flg[p]; flg[2*p] += flg[p];
	seg[2*p+1] += flg[p]; flg[2*p+1] += flg[p];
	flg[p] = 0;
}

void upd(int p, int l, int r, int L, int R) {
	push(p, l, r);
	if (R < l || r < L) return;
	if (L <= l && r <= R) {
		seg[p]++; flg[p]++;
		return;
	}
	int mid = (l + r)/2;
	upd(2*p, l, mid, L, R); upd(2*p+1, mid+1, r, L, R);
	seg[p] = max(seg[2*p], seg[2*p + 1]);
}

int qry(int p, int l, int r, int L, int R) {
	push(p, l, r);
	if (R < l || r < L) return -1;
	if (L <= l && r <= R) return seg[p];
	int mid = (l + r)/2;
	return max(qry(2*p, l, mid, L, R), qry(2*p+1, mid+1, r, L, R));
}

int fl(int p, int l, int r, int v) {
	push(p, l, r);
	if (l == r) return l + (seg[p] != v);
	int mid = (l + r) >> 1;
	if (seg[2*p + 1] <= v) return fl(2*p, l, mid, v);
	else return fl(2*p + 1, mid+1, r, v);
}

int fr(int p, int l, int r, int v) {
	push(p, l, r);
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (seg[2*p + 1] < v) return fr(2*p, l, mid, v);
	else return fr(2*p+1, mid+1, r, v);
}


int main() {
	cin >> n;

	for (int i = 0; i < n; i++) cin >> masts[i].first >> masts[i].second;

	sort(masts, masts + n);

	for (int i = 0; i < n; i++) {
		int ht = masts[i].first, k = masts[i].second;
		int maxv = qry(1, 0, maxh-1, ht-k, ht);
		int l = fl(1, 0, maxh-1, maxv), r = fr(1, 0, maxh-1, maxv);
		int numright = (ht - 1) - r;
		if (numright <= 0) 
			upd(1, 0, maxh-1, l, l + k - 1);
		  // {upd(1, 0, maxh-1, l, l + k - 1); cout << l << " " << l + k - 1 << endl; }
		else {
			// cout << r + 1 << " " << ht - 1 << " " << l << " " << l + (k - numright) -1 << endl;
			upd(1, 0, maxh-1, r + 1, ht - 1);
			upd(1, 0, maxh-1, l, l + (k - numright) - 1);
		}
	}

	long long ans = 0;
	for (int i = 0; i < maxh; i++) {
		long long x = qry(1, 0, maxh-1, i, i);
		ans += (long long)(x * (x - 1) / 2);
	}

	cout << ans << '\n';

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1020 KB Output is correct
2 Correct 22 ms 1104 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1084 KB Output is correct
2 Correct 25 ms 1092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1092 KB Output is correct
2 Correct 28 ms 1068 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1120 KB Output is correct
2 Correct 28 ms 1076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1076 KB Output is correct
2 Correct 33 ms 2260 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1500 KB Output is correct
2 Correct 86 ms 1628 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 1644 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2120 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 2824 KB Output is correct
2 Correct 206 ms 3840 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 2964 KB Output is correct
2 Correct 122 ms 3324 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 3112 KB Output is correct
2 Correct 208 ms 2200 KB Output is correct