oj.uz

Submission #230006

# Submission time Handle Problem Language Result Execution time Memory
230006 2020-05-07T17:06:04 Z DrSwad Sails (IOI07_sails) C++17
100 / 100
 68 ms 2680 KB 
#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

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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 640 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 22 ms 1280 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1280 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1656 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2176 KB Output is correct
2 Correct 45 ms 2296 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2528 KB Output is correct
2 Correct 50 ms 2172 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2680 KB Output is correct
2 Correct 49 ms 2556 KB Output is correct