Submission #583147

#	Time	Username	Problem	Language	Result	Execution time	Memory
583147		Shreyan_Paliwal	Sails (IOI07_sails)	C++17	100 / 100	251 ms	3840 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10