Submission #1108706

#TimeUsernameProblemLanguageResultExecution timeMemory
1108706vladiliusEscape Route 2 (JOI24_escape2)C++17
100 / 100
2463 ms33820 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second const ll inf = numeric_limits<ll> :: max(); int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, D; cin>>n>>D; vector<int> x(n); vector<pii> t[n]; for (int i = 1; i < n; i++){ cin>>x[i]; for (int j = 0; j < x[i]; j++){ int a, b; cin>>a>>b; t[i].pb({a, b}); } } for (int i = 1; i < n; i++){ sort(t[i].begin(), t[i].end()); vector<pii> nw; for (int j = 0; j < x[i]; j++){ while (!nw.empty() && nw.back().ss >= t[i][j].ss){ nw.pop_back(); } if (nw.empty() || nw.back().ff != t[i][j].ff){ nw.pb(t[i][j]); } } t[i] = nw; x[i] = (int) t[i].size(); } vector<int> p(n); for (int i = 1; i < n; i++){ p[i] = p[i - 1] + x[i]; } int S = p.back(); vector<int> g(S); vector<bool> e(S); for (int i = 1; i + 1 < n; i++){ int k = x[i + 1] - 1, mn = 0; for (int j = x[i] - 1; j >= 0; j--){ while (k >= 0 && t[i + 1][k].ff >= t[i][j].ss){ mn = k--; } g[p[i - 1] + j] = p[i] + mn; e[p[i - 1] + j] = (t[i][j].ss > t[i + 1][mn].ff); } } const int lg = log2(S); vector<vector<pii>> sp(S, vector<pii>(lg + 1)); for (int i = 0; i < S; i++) sp[i][0] = {g[i], e[i]}; for (int j = 1; j <= lg; j++){ for (int i = 0; i + (1 << j) <= S; i++){ sp[i][j] = {sp[sp[i][j - 1].ff][j - 1].ff, sp[i][j - 1].ss + sp[sp[i][j - 1].ff][j - 1].ss}; } } auto get = [&](int l, int r){ ll out = inf; for (int i = 0; i < x[l]; i++){ int tt = r - l - 1, f = p[l - 1] + i, cc = 0; for (int j = lg; j >= 0; j--){ int k = (1 << j); if (tt >= k){ cc += sp[f][j].ss; f = sp[f][j].ff; tt -= k; } } out = min(out, 1LL * D * cc + (t[r - 1][f - p[r - 2]].ss - t[l][i].ff)); } return out; }; vector<vector<ll>> out; vector<int> all; const int A = 300; ll mn; for (int i = 1; i < n; i++){ if (x[i] <= A) continue; all.pb(i); vector<pair<int, ll>> st, nw; for (int j = 0; j < x[i]; j++){ st.pb({p[i - 1] + j, t[i][j].ss - t[i][j].ff}); } vector<ll> add; for (int j = 0; j <= i; j++) add.pb(0); for (int j = i + 1; j <= n; j++){ mn = inf; for (auto [x, y]: st){ mn = min(mn, y); } add.pb(mn); if (j == n) break; for (auto& [x, y]: st){ y += D * e[x] + (t[j][g[x] - p[j - 1]].ss - t[j - 1][x - p[j - 2]].ss); x = g[x]; } nw.clear(); int k = 0; while (k < st.size()){ int h = k; mn = inf; while (h < st.size() && st[k].ff == st[h].ff){ mn = min(mn, st[h].ss); h++; } nw.pb({st[k].ff, mn}); k = h; } st = nw; } out.pb(add); } vector<int> :: iterator it; int q; cin>>q; for (int i = 1; i <= q; i++){ int l, r; cin>>l>>r; if (x[l] <= A){ cout<<get(l, r)<<"\n"; } else { it = lower_bound(all.begin(), all.end(), l); int j = (int) (it - all.begin()); cout<<out[j][r]<<"\n"; } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while (k < st.size()){
      |                    ~~^~~~~~~~~~~
Main.cpp:114:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 while (h < st.size() && st[k].ff == st[h].ff){
      |                        ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...