Submission #52463

#TimeUsernameProblemLanguageResultExecution timeMemory
52463ics0503Pinball (JOI14_pinball)C++17
0 / 100
2 ms248 KiB
#include<stdio.h> #include<algorithm> using namespace std; struct xy {long long a, b, c, d;}a[121212]; long long ALL[414141], an = 0; long long F(long long x) { return (lower_bound(ALL, ALL + an, x) - ALL); } long long tree[2][1212121], tn; long long min(long long a, long long b) { if (a < b)return a; return b; } void insert_g(long long tp, long long w, long long g) { for (long long i = tn + w; i > 0; i /= 2)tree[tp][i] = min(tree[tp][i], g); } long long search_g(long long tp, long long ss, long long ee) { long long s = ss + tn, e = ee + tn; long long res = 1e18; while (s <= e) { if (s % 2 == 1)res = min(res, tree[tp][s++]); if (e % 2 == 0)res = min(res, tree[tp][e--]); s /= 2; e /= 2; } return res; } int main() { long long n, m; scanf("%lld%lld", &m, &n); long long i, j; for (i = 0; i < m; i++) { scanf("%lld%lld%lld%lld", &a[i].a, &a[i].b, &a[i].c, &a[i].d); ALL[an++] = a[i].a; ALL[an++] = a[i].b; ALL[an++] = a[i].c; } ALL[an++] = 1; ALL[an++] = n; sort(ALL, ALL + an); an = unique(ALL, ALL + an) - ALL; for (tn = 1; tn < an; tn *= 2); for (i = 0; i < m; i++) a[i] = { F(a[i].a), F(a[i].b), F(a[i].c), a[i].d }; for (i = 0; i < tn * 2; i++)tree[0][i] = tree[1][i] = 1e18; long long ans = 1e18; for (i = 0; i < m; i++) { long long l = (a[i].a == 0 ? 0 : search_g(0, a[i].a, a[i].b))+a[i].d; long long r = (a[i].b == n-1 ? 0 : search_g(1, a[i].a, a[i].b))+a[i].d; ans = min(ans, l + r - a[i].d); insert_g(0, a[i].c, l); insert_g(1, a[i].c, r); } if (ans > 1e17)printf("-1"); else printf("%lld", ans); return 0; }

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:22:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j;
               ^
pinball.cpp:21:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, m; scanf("%lld%lld", &m, &n);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
pinball.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...