oj.uz

Submission #119088

# Submission time Handle Problem Language Result Execution time Memory
119088 2019-06-20T10:07:21 Z Bruteforceman Cambridge (info1cup18_cambridge) C++11
100 / 100
 132 ms 10232 KB 
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
int t[100010], d[100010];
int opt[100010];
int order[100010];
int pos[100010];

long long sum[100010 * 4];
long long ans[100010 * 4];
const long long inf = 1e18;

int n;

bool cmp(int p, int q) {
	if(d[p] == d[q]) {
		return t[p] < t[q];
	}
	return d[p] < d[q];
}

void add(int x, int c = 1, int b = 1, int e = n) {
	if(b == e) {
		sum[c] = t[order[b]];
		ans[c] = d[order[b]] - t[order[b]];
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) {
		add(x, l, b, m);
	} else {
		add(x, r, m + 1, e);
	}
	sum[c] = sum[l] + sum[r];
	ans[c] = min(ans[l], ans[r] - sum[l]);
}

void del(int x, int c = 1, int b = 1, int e = n) {
	if(b == e) {
		sum[c] = 0;
		ans[c] = inf;
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) {
		del(x, l, b, m);
	} else {
		del(x, r, m + 1, e);
	}
	sum[c] = sum[l] + sum[r];
	ans[c] = min(ans[l], ans[r] - sum[l]);
}

int main(int argc, char const *argv[])
{
	int m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &t[i], &d[i]);
		order[i] = i;
		del(i);
	}
	sort(order + 1, order + n + 1, cmp);
	for(int i = 1; i <= n; i++) {
		pos[order[i]] = i;
	}
	int cur = n;
	for(int i = n; i >= 1; i--) {
		add(pos[i]);
		while(cur >= i && ans[1] <= 0) {
			del(pos[cur--]);
		}
		opt[i] = cur;
	}
	while(m--) {
		int p, q;
		scanf("%d %d", &p, &q);
		printf("%d\n", (opt[p] >= q));
	}
	return 0;
}

Compilation message

cambridge.cpp: In function 'int main(int, const char**)':
cambridge.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
cambridge.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t[i], &d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cambridge.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 94 ms 6372 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 9 ms 1280 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 16 ms 512 KB Output is correct
4 Correct 30 ms 632 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 94 ms 6372 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 9 ms 1280 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 30 ms 632 KB Output is correct
8 Correct 125 ms 8032 KB Output is correct
9 Correct 132 ms 9436 KB Output is correct
10 Correct 122 ms 9540 KB Output is correct
11 Correct 96 ms 10232 KB Output is correct
12 Correct 120 ms 9468 KB Output is correct
13 Correct 2 ms 384 KB Output is correct