Submission #56552

#	Time	Username	Problem	Language	Result	Execution time	Memory
56552		ruhanhabib39	Pinball (JOI14_pinball)	C++17	100 / 100	994 ms	78256 KiB

pinball

#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1e5;
const int MX = 4 * MAXM + 10;
const long long INF = 1e18;

struct dat {
   long long a, b, c, d;
};

ostream& operator<<(ostream& os, dat d) {
   return os << "{[" << d.a << ", " << d.b << "] " << d.c << " " << d.d << "}";
}

long long N, M;
dat dt[MAXM + 10];
long long mn[3 * MX + 10];
long long pref[MAXM + 10], suff[MAXM + 10];

void compress() {
   set<int> st;
   for(int i = 1; i <= M; i++) {
      st.insert(dt[i].a);
      st.insert(dt[i].b);
      st.insert(dt[i].c);
   }
   map<int,int> mp;
   int ii = 0;
   for(int x : st) mp[x] = ++ii;
   for(int i = 1; i <= M; i++) {
      dt[i].a = mp[dt[i].a];
      dt[i].b = mp[dt[i].b];
      dt[i].c = mp[dt[i].c];
   }
   if(!st.count(1) || !st.count(N)) {
      printf("-1\n");
      exit(0);
   }
   N = ii;
}

void upd(int i, long long x) {
   i--; // 0-based
   i += N;
   for(mn[i] = min(mn[i], x); i > 1; i >>= 1) {
      mn[i >> 1] = min(mn[i], mn[i ^ 1]);
   }
}

long long get(int l, int r) {
   l--; r--; r++; // now [l, r), 0 based
   long long res = INF;
   for(l += N, r += N; l < r; l >>= 1, r >>= 1) {
      if(l & 1) res = min(res, mn[l++]);
      if(r & 1) res = min(res, mn[--r]);
   }
   return res;
}

void reset() {
   fill(mn, mn + N+N+10, INF);
}

int main() {
   scanf("%lld%lld", &M, &N);
   for(int i = 1; i <= M; i++) {
      scanf("%lld%lld%lld%lld", &dt[i].a, &dt[i].b, &dt[i].c, &dt[i].d);
   }
   compress();
   reset();
   fill(pref, pref + M + 1, INF);
   for(int j = 1; j <= M; j++) {
      if(dt[j].a == 1) pref[j] = 0;
      else pref[j] = min(INF, get(dt[j].a, dt[j].b));
      if(pref[j] < INF) upd(dt[j].c, dt[j].d + pref[j]);
   }

   reset();
   fill(suff, suff + M + 1, INF);
   for(int j = 1; j <= M; j++) {
      if(dt[j].b == N) suff[j] = 0;
      else suff[j] = min(INF, get(dt[j].a, dt[j].b));
      if(suff[j] < INF) upd(dt[j].c, dt[j].d + suff[j]);
   }
   long long res = INF;
   for(int i = 1; i <= M; i++) {
      res = min(res, pref[i] + suff[i] + dt[i].d);
   }
   if(res == INF) res = -1;
   printf("%lld\n", res);
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &M, &N);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
pinball.cpp:68:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld%lld%lld%lld", &dt[i].a, &dt[i].b, &dt[i].c, &dt[i].d);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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