Submission #1162905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162905		Zero_OP	Marathon Race 2 (JOI24_ho_t3)	C++20	62 / 100	1595 ms	49536 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 5e5 + 5;
const int MAXDIFF = 1005;

int N, L, M, X[MAX], v[MAX], c[MAX], pref[MAX], suff[MAX];
ll f[MAXDIFF][MAXDIFF][2], g[MAXDIFF][MAXDIFF][2];
//f[l][r][t] : [1...l] [r...N]] (l < r) if t = 0 : at L, t = 1 : at R, take the leftmost balls first
//f[l][r][t] : [1...l] [r...N]] (l < r) if t = 0 : at L, t = 1 : at R, take the rightmost balls first

ll dp_start_1[MAX][2]; //0 : v[i] > G, 1 : v[i] < G
ll dp_start_M[MAX][2]; //0 : v[i] > G, 1 : v[i] < G

int query_balls(int l, int r){
      if(l > r) return 0;
      assert(1 <= l && r <= M);
      assert((pref[r] - pref[l-1]) > 0);
      return pref[r] - pref[l-1];
}

int main(){
      setIO();

      cin >> N >> L;
      FOR(i, 0, N){
            cin >> X[i];
      }

      sort(X, X + N);
      FOR(i, 0, N){
            if(!M || v[M] != X[i]){
                  ++M;
                  v[M] = X[i];
                  c[M] = 1;
            } else ++c[M];
      }

//      FOR(i, 1, M+1) cout << v[i] << ' ' << c[i] << '\n'; cout << '\n';

      int Q;
      cin >> Q;

      const int BOUND = 5e5;
      if(M > 1000){
            while(Q--){
                  int S, G, T;
                  cin >> S >> G >> T;
                  cout << "No\n";
            }
            return 0;
      }

      FOR(i, 1, M+2) pref[i] = pref[i-1] + c[i];
      ROF(i, M+1, 1) suff[i] = suff[i+1] + c[i];

      memset(f, 0x3f, sizeof(f));
      memset(g, 0x3f, sizeof(g));

      const ll inf = f[0][0][0];

      f[1][M+1][0] = 0;
      g[0][M][1] = 0;

      for(int len = M; len >= 1; --len){
            for(int l = 0, r = len; r <= M+1; ++l, ++r){
                  if(f[l][r][0] != inf){
                        //move to l+1
                        minimize(f[l+1][r][0], f[l][r][0] + 1LL * (pref[l] + suff[r] + 1) * (v[l+1] - v[l]));
                        //move to r-1
                        minimize(f[l][r-1][1], f[l][r][0] + 1LL * (pref[l] + suff[r] + 1) * (v[r-1] - v[l]));
                  }

                  if(f[l][r][1] != inf){
                        //move to l+1
                        minimize(f[l+1][r][0], f[l][r][1] + 1LL * (pref[l] + suff[r] + 1) * (v[r] - v[l+1]));
                        //move to r-1
                        minimize(f[l][r-1][1], f[l][r][1] + 1LL * (pref[l] + suff[r] + 1) * (v[r] - v[r-1]));
                  }

                  if(g[l][r][0] != inf){
                        //move to l+1
                        minimize(g[l+1][r][0], g[l][r][0] + 1LL * (pref[l] + suff[r] + 1) * (v[l+1] - v[l]));
                        //move to r-1
                        minimize(g[l][r-1][1], g[l][r][0] + 1LL * (pref[l] + suff[r] + 1) * (v[r-1] - v[l]));
                  }

                  if(g[l][r][1] != inf){
                        //move to l+1
                        minimize(g[l+1][r][0], g[l][r][1] + 1LL * (pref[l] + suff[r] + 1) * (v[r] - v[l+1]));
                        //move to r-1
                        minimize(g[l][r-1][1], g[l][r][1] + 1LL * (pref[l] + suff[r] + 1) * (v[r] - v[r-1]));

                  }
            }
      }

      memset(dp_start_1, 0x3f, sizeof(dp_start_1));
      memset(dp_start_M, 0x3f, sizeof(dp_start_M));

      FOR(i, 1, M+1){
            //find all state that start somewhere and end at v[i]
            //f[i-1][i][1] : start at v[1], end at v[i] -> abs(S - v[1]) + abs(G - v[i]) * (N+1) + f[i-1][i][1]
            //f[i][i+1][0] : start at v[1], end at v[i] -> abs(S - v[1]) + abs(G - v[i]) * (N+1) + f[i][i+1][0]

            //g[i-1][i][1] : start at v[M], end at v[i] -> abs(S - v[M]) + abs(G - v[i]) * (N+1) + g[i-1][i][1]
            //g[i][i+1][0] : start at v[M], end at v[i] -> abs(S - v[M]) + abs(G - v[i]) * (N+1) + g[i][i+1][0]

//            cout << f[i-1][i][1] << ' ' << f[i][i+1][0] << ' ';
//            cout << g[i-1][i][1] << ' ' << g[i][i+1][0] << '\n';

            minimize(dp_start_1[v[i]][0], f[i-1][i][1] + 1LL * v[i] * (N+1));
            minimize(dp_start_1[v[i]][1], f[i-1][i][1] - 1LL * v[i] * (N+1));
            minimize(dp_start_1[v[i]][0], f[i][i+1][0] + 1LL * v[i] * (N+1));
            minimize(dp_start_1[v[i]][1], f[i][i+1][0] - 1LL * v[i] * (N+1));

            minimize(dp_start_1[v[i]][0], g[i-1][i][1] + 1LL * v[i] * (N+1));
            minimize(dp_start_1[v[i]][1], g[i-1][i][1] - 1LL * v[i] * (N+1));
            minimize(dp_start_1[v[i]][0], g[i][i+1][0] + 1LL * v[i] * (N+1));
            minimize(dp_start_1[v[i]][1], g[i][i+1][0] - 1LL * v[i] * (N+1));
      }

      FOR(i, 1, BOUND+1) {
            minimize(dp_start_1[i][1], dp_start_1[i-1][1]);
            minimize(dp_start_M[i][1], dp_start_M[i-1][1]);
      }

      ROF(i, BOUND+1, 0){
            minimize(dp_start_1[i][0], dp_start_1[i+1][0]);
            minimize(dp_start_M[i][0], dp_start_M[i+1][0]);
      }

//      cout << f[2][3][0] << '\n';

      ll all_left = 0;
      ll all_right = 0;
      int s = 0;

      FOR(i, 1, M) {
            s += c[i];
            all_left += 1LL * (v[i+1] - v[i]) * (s+1);
      }

      s = 0;
      ROF(i, M, 1) {
            s += c[i+1];
            all_right += 1LL * (v[i+1] - v[i]) * (s+1);
      }

//      cout << g[4][5][0] << '\n';

      while(Q--){
            int S, G, T;
            cin >> S >> G >> T;

            //0 : v[i] > G, 1 : v[i] < G
            ll best = min(abs(S - v[1]) + all_left + 1LL * abs(G - v[M]) * (N+1),
                          abs(S - v[M]) + all_right + 1LL * abs(G - v[1]) * (N+1));
            FOR(i, 1, M+1){
//                  ll a = abs(S - v[1]) + abs(G - v[i]) * (N+1) + f[i-1][i][1];
//                  ll b = abs(S - v[1]) + abs(G - v[i]) * (N+1) + f[i][i+1][0];
//                  ll c = abs(S - v[M]) + abs(G - v[i]) * (N+1) + g[i-1][i][1];
//                  ll d = abs(S - v[M]) + abs(G - v[i]) * (N+1) + g[i][i+1][0];
//                  cout << dbg(a) << dbg(b) << dbg(c) << dbg(d) << '\n';
                  if(f[i-1][i][1] != inf) minimize(best, abs(S - v[1]) + abs(G - v[i]) * (N+1) + f[i-1][i][1]);
                  if(f[i][i+1][0] != inf) minimize(best, abs(S - v[1]) + abs(G - v[i]) * (N+1) + f[i][i+1][0]);
                  if(g[i-1][i][1] != inf) minimize(best, abs(S - v[M]) + abs(G - v[i]) * (N+1) + g[i-1][i][1]);
                  if(g[i][i+1][0] != inf) minimize(best, abs(S - v[M]) + abs(G - v[i]) * (N+1) + g[i][i+1][0]);
//                  cout << dbg(best) << '\n';
            }
            best += N;
//                  cout << best << '\n';
            cout << (best <= T ? "Yes\n" : "No\n");
      }

      return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19