oj.uz

Submission #54711

# Submission time Handle Problem Language Result Execution time Memory
54711 2018-07-04T17:56:46 Z 0^0(#1466) Sails (IOI07_sails) C++11
90 / 100
 1000 ms 9568 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int tree[1 << 18][2];
int n;
pair<int, int> arr[100005];
void push(int nodele, int noderi, int node) {
	tree[node][0] += (noderi - nodele + 1)*tree[node][1];
	if (nodele != noderi) {
		tree[node * 2][1] += tree[node][1];
		tree[node * 2 + 1][1] += tree[node][1];
	}
	tree[node][1] = 0;
}
void update(int le, int ri, int val, int nodele, int noderi, int node) {
	push(nodele, noderi, node);
	if (le > noderi || ri < nodele)return;
	if (le <= nodele && noderi <= ri) {
		tree[node][1] += val;
		push(nodele, noderi, node);
		return;
	}
	int mid = (nodele + noderi) / 2;
	update(le, ri, val, nodele, mid, node * 2);
	update(le, ri, val, mid + 1, noderi, node * 2 + 1);
	tree[node][0] = tree[node * 2][0] + tree[node * 2 + 1][0];
}
void update(int le, int ri, int val) {
	update(le, ri, val, 1, 100000, 1);
}
int query(int le, int ri, int nodele, int noderi, int node) {
	push(nodele, noderi, node);
	if (le > noderi || ri < nodele)return 0;
	if (le <= nodele && noderi <= ri) return tree[node][0];
	int mid = (nodele + noderi) / 2;
	return query(le, ri, nodele, mid, node * 2) + query(le, ri, mid + 1, noderi, node * 2 + 1);
}
int query(int le, int ri) {
	return query(le, ri, 1, 100000, 1);
}
int get_idx(ll x) {
	int ret = 0;
	int le, ri, mid;
	le = 1;
	ri = 100000;
	while (le <= ri) {
		mid = (le + ri) / 2;
		if (query(mid, mid) >= x) {
			ret = mid;
			le = mid + 1;
		}
		else ri = mid - 1;
	}
	return ret;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d", &arr[i].first, &arr[i].second);
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		int h, k;
		tie(h, k) = arr[i];
		int le = h - k + 1;
		if (le == 1 || query(le, le) != query(le - 1, le - 1)) {
			update(le, h, 1);
		}
		else {
			int idx = get_idx(query(le, le));
			if (query(le, le)) {
				update(idx + 1, h, 1);
				k -= h - idx;
			}
			idx = get_idx(query(le, le) + 1);
			update(idx + 1, idx + k, 1);
		}
	}
	ll ans = 0;
	for (int i = 1; i <= 100000; i++) {
		ll temp = query(i, i);
		ans += temp * (temp - 1) / 2;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sails.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &arr[i].first, &arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2424 KB Output is correct
2 Correct 29 ms 2520 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2520 KB Output is correct
2 Correct 29 ms 2520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2556 KB Output is correct
2 Correct 29 ms 2564 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2568 KB Output is correct
2 Correct 34 ms 2572 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2600 KB Output is correct
2 Correct 41 ms 2616 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2824 KB Output is correct
2 Correct 378 ms 3424 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 3796 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 4536 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 5640 KB Output is correct
2 Correct 846 ms 6520 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 7852 KB Output is correct
2 Correct 978 ms 8460 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 9568 KB Time limit exceeded
2 Halted 0 ms 0 KB -