oj.uz

Submission #538524

# Submission time Handle Problem Language Result Execution time Memory
538524 2022-03-17T03:52:28 Z Cantfindme Sails (IOI07_sails) C++17
100 / 100
 50 ms 3896 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2116 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3376 KB Output is correct
2 Correct 35 ms 3408 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3648 KB Output is correct
2 Correct 37 ms 3156 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3896 KB Output is correct
2 Correct 34 ms 3316 KB Output is correct