Submission #314258

#TimeUsernameProblemLanguageResultExecution timeMemory
314258lauranPinball (JOI14_pinball)C++14
100 / 100
823 ms49272 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const ll INF = 1e17; const int NMAX = 1e6 + 5; int m, n; int A[NMAX], B[NMAX], C[NMAX], D[NMAX]; ll dpst[NMAX], dpdr[NMAX]; ll poz, val; ll st, dr, ansQuery; ll aint[2][4 * NMAX]; void normalizare() { // normalizez 1, A, B, C, n set <int> tot; tot.insert(1); tot.insert(n); for (int i = 1; i <= m; i++) { tot.insert(A[i]); tot.insert(B[i]); tot.insert(C[i]); } map <int, int> nou; int newN = 0; for (auto x: tot) nou[x] = ++newN; for (int i = 1; i <= m; i++) { A[i] = nou[A[i]]; B[i] = nou[B[i]]; C[i] = nou[C[i]]; } n = newN; } void build(int lin, int nod, int l, int r) { if (l == r) { aint[lin][nod] = INF; return; } int mij = (l + r) / 2; build(lin, 2 * nod, l, mij); build(lin, 2 * nod + 1, mij + 1, r); aint[lin][nod] = INF; } void update(int lin, int nod, int l, int r) { if (l == r) { if (val < aint[lin][nod]) aint[lin][nod] = val; return; } int mij = (l + r) / 2; if (poz <= mij) update(lin, 2 * nod, l, mij); else update(lin, 2 * nod + 1, mij + 1, r); aint[lin][nod] = min(aint[lin][2 * nod], aint[lin][2 * nod + 1]); } void query(int lin, int nod, int l, int r) { if (st <= l && r <= dr) { ansQuery = min(ansQuery, aint[lin][nod]); return; } int mij = (l + r) / 2; if (st <= mij) query(lin, 2 * nod, l, mij); if (dr > mij) query(lin, 2 * nod + 1, mij + 1, r); } int main() { scanf("%d%d", &m, &n); for (int i = 1; i <= m; i++) { scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]); } normalizare(); build(0, 1, 1, n); build(1, 1, 1, n); if (A[1] == 1) dpst[1] = D[1]; else dpst[1] = INF; poz = C[1], val = dpst[1]; update(0, 1, 1, n); if (B[1] == n) dpdr[1] = D[1]; else dpdr[1] = INF; poz = C[1], val = dpdr[1]; update(1, 1, 1, n); for (int i = 2; i <= m; i++) { // dpst[i] = min{dpst[j] + d[i], cu C[j] intre A[i] si B[i]} dpst[i] = INF; if (A[i] == 1) dpst[i] = D[i]; else { st = A[i], dr = B[i]; ansQuery = INF; query(0, 1, 1, n); dpst[i] = min(dpst[i], ansQuery + D[i]); } poz = C[i], val = dpst[i]; update(0, 1, 1, n); dpdr[i] = INF; if (B[i] == n) dpdr[i] = D[i]; else { st = A[i], dr = B[i]; ansQuery = INF; query(1, 1, 1, n); dpdr[i] = min(dpdr[i], ansQuery + D[i]); } poz = C[i], val = dpdr[i]; update(1, 1, 1, n); } ll ans = INF; for (int i = 1; i <= m; i++) ans = min(ans, dpst[i] + dpdr[i] - D[i]); ans < INF ? printf("%lld", ans) : printf("-1"); return 0; }

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |    scanf("%d%d", &m, &n);
      |    ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:84:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |       scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...