Submission #882227

#TimeUsernameProblemLanguageResultExecution timeMemory
882227rainboyCambridge (info1cup18_cambridge)C11
100 / 100
62 ms9968 KiB
#include <stdio.h> #define N 100000 #define N_ (1 << 17) /* N_ = pow2(ceil(log2(N))) */ #define INF 0x3f3f3f3f3f3f3f3fLL long long min(long long a, long long b) { return a < b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int xx[N], yy[N]; void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (yy[ii[j]] == yy[i_]) j++; else if (yy[ii[j]] < yy[i_]) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } long long ss[N_ * 2], st[N_ * 2]; int n_; void pul(int i) { int l = i << 1, r = l | 1; ss[i] = ss[l] + ss[r]; st[i] = min(st[l], st[r] == INF ? INF : st[r] - ss[l]); } void build(int n) { int i; n_ = 1; while (n_ < n) n_ <<= 1; for (i = 0; i < n_; i++) st[n_ + i] = INF; for (i = n_ - 1; i > 0; i--) pul(i); } void update(int i, int x, long long y) { i += n_; ss[i] = x, st[i] = y == INF ? INF : y - x; while (i > 1) pul(i >>= 1); } int main() { static int ii[N], idx[N], jj[N]; int n, q, i, j; scanf("%d%d", &n, &q); for (i = 0; i < n; i++) scanf("%d%d", &xx[i], &yy[i]), yy[i]--; for (i = 0; i < n; i++) ii[i] = i; sort(ii, 0, n); for (i = 0; i < n; i++) idx[ii[i]] = i; build(n); for (i = 0, j = -1; i < n; i++) { while (j < n && st[1] >= 0) { j++; if (j == n) break; update(idx[j], xx[j], yy[j]); } jj[i] = j; update(idx[i], 0, INF); } while (q--) { scanf("%d%d", &i, &j), i--, j--; printf(j < jj[i] ? "1\n" : "0\n"); } return 0; }

Compilation message (stderr)

cambridge.c: In function 'main':
cambridge.c:68:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cambridge.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d", &xx[i], &yy[i]), yy[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cambridge.c:88:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...