oj.uz

Submission #583140

# Submission time Handle Problem Language Result Execution time Memory
583140 2022-06-24T22:06:47 Z Shreyan_Paliwal Sails (IOI07_sails) C++17
60 / 100
 257 ms 4168 KB 
#include <bits/stdc++.h>

using namespace std;

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

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 bld(int p, int l, int r) {
// 	if (l == r) {
// 		seg[p] = masts[p];
// 		return;
// 	}
// 	int mid = (l + r)/2;
// 	bld(2*p, l, mid);
// 	bld(2*p+1, mid+1, r);
// 	seg[p] = max(seg[2*p], seg[2*p + 1]);
// }

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, n-1, ht-k, ht);
		int l = fl(1, 0, n-1, maxv), r = fr(1, 0, n-1, maxv);
		int numright = (ht - 1) - r;
		if (numright <= 0) 
			upd(1, 0, n-1, l, l + k - 1);
		  // {upd(1, 0, n-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, n-1, r + 1, ht - 1);
			upd(1, 0, n-1, l, l + (k - numright) - 1);
		}
	}

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

	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 1332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 2268 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 4168 KB Output is correct
2 Correct 185 ms 3276 KB Output is correct