Submission #314258

#	Time	Username	Problem	Language	Result	Execution time	Memory
314258		lauran	Pinball (JOI14_pinball)	C++14	100 / 100	823 ms	49272 KiB

pinball

#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]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49