Submission #538524

#	Time	Username	Problem	Language	Result	Execution time	Memory
538524		Cantfindme	Sails (IOI07_sails)	C++17	100 / 100	50 ms	3896 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

int n;
int mx;

int fw[maxn];
int ls (int x) {
	return x & (-x);
}

void upd(int x, int y, int nv) {
	y++;
	for (; x <= mx+1; x += ls(x)) fw[x] += nv;
	for (; y <= mx+1; y += ls(y)) fw[y] -= nv;
}

int query(int x) { //Return rightmost index that is v > x.
	int sum = 0, index = 0;
	for (int k = (1 << 19); k; k >>= 1) {
		if ((index + k <= mx+1) and (sum + fw[index + k] > x)) {
			index += k;
			sum += fw[index];
		}
	}
	return index;
}

int rq(int x) {
	int sum = 0;
	for (; x; x -= ls(x)) {
		sum += fw[x];
	}
	return sum;
}

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	cin >> n;
	vector <pi> v;
	for (int i =1;i<=n;i++) {
		int h,k; cin >> h >> k;
		v.push_back(pi(h,k));
	}

	sort(all(v));
	mx = v.back().f;

	for (auto [h, k] : v) {
		//We +1 to [h - k + 1, h]

		int v = rq(h - k + 1);
		int l = query(v) + 1;
		int r = query(v - 1);

		if (r < h) {
			int solve = h - r;
			k -= solve;
			upd(r + 1, h, 1);
		}

		upd(l, l + k - 1, 1);
	}

	int rans = 0;
	for (int h = 1; h <= mx; h++) {
		int val = rq(h);
		rans += (val * (val-1) / 2);
	}
	cout << rans;
}

• 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