Submission #382585

#TimeUsernameProblemLanguageResultExecution timeMemory
382585rainboyStrange Device (APIO19_strange_device)C11
15 / 100
546 ms40044 KiB
#include <stdio.h> #define N 1000000 long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } long long 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) { long long c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[ii[j]] - yy[i_]; if (c == 0) j++; else if (c < 0) { 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; } } int main() { static int ii[N]; int n, n_, i, ans; long long a, b; scanf("%d%lld%lld", &n, &a, &b); if (n == 1) { long long l, r, k; scanf("%lld%lld", &l, &r); k = a / gcd(a, b + 1); printf("%lld\n", k <= (r - l + 1) / b ? k * b : r - l + 1); return 0; } n_ = 0; while (n--) { long long l, r; scanf("%lld%lld", &l, &r); while (l <= r) { xx[n_] = (l + l / b) % a, yy[n_] = l % b, n_++; l++; } } n = n_; for (i = 0; i < n; i++) ii[i] = i; sort(ii, 0, n); ans = 1; for (i = 1; i < n; i++) if (xx[ii[i]] != xx[ii[i - 1]] || yy[ii[i]] != yy[ii[i - 1]]) ans++; printf("%d\n", ans); return 0; }

Compilation message (stderr)

strange_device.c: In function 'main':
strange_device.c:44:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%lld%lld", &n, &a, &b);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.c:48:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf("%lld%lld", &l, &r);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.c:57:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%lld%lld", &l, &r);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...