Submission #230006

#	Time	Username	Problem	Language	Result	Execution time	Memory
230006		DrSwad	Sails (IOI07_sails)	C++17	100 / 100	68 ms	2680 KiB

sails

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second

#ifdef LOCAL
#include "/Users/swad/Desktop/CP/debug.h"
#endif

const int N = int(1e5) + 10;
const int LOGN = 16;

int n;
pii p[N];

int ft[N];
void add(int at, int v) {
	while (at < N) ft[at] += v, at += at & -at;
}
int query(int at) {
	int ret = 0;
	while (at > 0) ret += ft[at], at -= at & -at;
	return ret;
}

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d %d", &p[i].x, &p[i].y);

	sort(p + 1, p + n + 1);

	for (int i = 1; i <= n; i++) {
		int at = p[i].x - p[i].y + 1;
		int v = query(at);

		int L = 0, vL = 0;
		for (int len = LOGN; len >= 0; len--) {
			if (L + (1 << len) >= N) continue;
			if (vL + ft[L + (1 << len)] > v) {
				vL += ft[L + (1 << len)];
				L += 1 << len;
			}
		}
		L++;

		int R = 0, vR = 0;
		for (int len = LOGN; len >= 0; len--) {
			if (R + (1 << len) >= N) continue;
			if (vR + ft[R + (1 << len)] >= v) {
				vR += ft[R + (1 << len)];
				R += 1 << len;
			}
		}
		R = min(R, p[i].x);

		if (R + 1 < N) add(R + 1, 1);
		if (p[i].x + 1 < N) add(p[i].x + 1, -1);

		int rem = p[i].y - (p[i].x - R);
		add(L, 1);
		if (L + rem < N) add(L + rem, -1);
	}

	ll ans = 0LL;
	for (int i = 1; i < N; i++) {
		ft[i] += ft[i & (i - 1)];
		ans += (ll)ft[i] * (ft[i] - 1) / 2;
	}

	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sails.cpp:37:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d %d", &p[i].x, &p[i].y);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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