Submission #1162314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162314		Zero_OP	Marathon Race 2 (JOI24_ho_t3)	C++20	0 / 100	0 ms	328 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 compact(v) v.erase(unique(all(v)), end(v))

#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 vd = vector<db>;

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;


int N, L, Q, X[MAX], pref[MAX], suff[MAX], d[MAX];
ll sum_pref_d[MAX], sum_suff_d[MAX];
vpi v;

int query_collected(int l, int r){
      return pref[r] - (l > 0 ? pref[l-1] : 0);
}

ll query_sum_pref_d(int l, int r){
      if(l > r) return 0;
      return sum_pref_d[r] - (l > 0 ? sum_pref_d[l-1] : 0);
}

ll query_sum_suff_d(int l, int r){
      if(l > r) return 0;
      return sum_suff_d[l] - sum_suff_d[r+1];
}

ll calc(int i, int j, int k){
      ll cost = 0;

      int visited = 0;
      if(i < j){
            cost += v[j].ff - v[i].ff + query_sum_suff_d(i, j-1);
            visited = query_collected(i, j);
      } else{
            cost += v[i].ff - v[j].ff + query_sum_pref_d(j, i-1);
            visited = query_collected(j, i);
      }

      if(i < k){
            cost += 1LL * visited * (v[k].ff - v[i].ff) + query_sum_pref_d(i, k-1);
      } else{
            cost += 1LL * visited * (v[k].ff - v[i].ff) + query_sum_suff_d(k, i-1);
      }

      return cost;
}

int main(){
      setIO();

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

      sort(X, X + N);
      FOR(i, 0, N){
            if(v.empty() || v.back().ff != X[i]) v.eb(X[i], 1);
            else ++v.back().ss;
      }

      FOR(i, 0, sz(v)-1) d[i] = v[i+1].ff - v[i].ff;
      FOR(i, 0, sz(v)) pref[i] = (i > 0 ? pref[i-1] : 0) + v[i].ss;
      ROF(i, sz(v), 0) suff[i] = (i+1 < sz(v) ? suff[i+1] : 0) + v[i].ss;
      FOR(i, 0, sz(v)-1) sum_pref_d[i] = (i > 0 ? sum_pref_d[i-1] : 0) + 1LL * (pref[i]+1) * d[i];
      ROF(i, sz(v)-1, 0) sum_suff_d[i] = sum_suff_d[i+1] + 1LL * (suff[i]+1) * d[i];

      int m = sz(v);

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

//            cout << S << ' ' << G << ' ' << T << '\n';

            ll best = 1e18;
            FOR(i, sz(v)-1, sz(v)){
                  minimize(best, calc(i, 0, m-1) + abs(S - v[i].ff) + 1LL * (N+1) * abs(G - v[m-1].ff));
                  minimize(best, calc(i, m-1, 0) + abs(S - v[i].ff) + 1LL * (N+1) * abs(G - v[0].ff));
            }

            best += N;
//            cout << best << '\n';
            cout << (best <= T ? "Yes\n" : "No\n");
      }

      return 0;
}

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