Submission #1152151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152151		abczz	Train (APIO24_train)	C++20	40 / 100	393 ms	236828 KiB

train

#include "train.h"
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <algorithm>
#include <map>
#define ll long long

using namespace std;

vector <array<ll, 3>> Q;
vector <ll> U;
vector <array<ll, 2> > V;
vector <ll> VB;
map <ll, ll> rmp[200010];
map <ll, ll> mp;
ll dp[200005], rb[200005], G[200005], rmv[200005], gb;
deque <array<ll, 2> > dq[200005];

struct SegTree{
  ll st[400020], lazy[400020];
  void init() {
    for (int i=0; i<(ll)4e5+20; ++i) {
      st[i] = lazy[i] = 0;
    }
  }
  void push(ll id) {
    st[id*2] += lazy[id];
    st[id*2+1] += lazy[id];
    lazy[id*2] += lazy[id];
    lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
  }
  void range_update(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      ++st[id], ++lazy[id];
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    range_update(id*2, l, mid, ql, qr);
    range_update(id*2+1, mid+1, r, ql, qr);
    st[id] = min(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll q) {
    if (l == r) return st[id];
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) return query(id*2, l, mid, q);
    else return query(id*2+1, mid+1, r, q);
  }
}ST;
vector <ll> rt, S;
vector <ll> ldis;
struct PerstSegTree{
  struct Node{
    ll val = 0;
    ll chl = -1;
    ll chr = -1;
  };
  vector <Node> st;
  ll New() {
    st.push_back({0, -1, -1});
    return (ll)st.size()-1;
  }
  void build(ll id, ll l, ll r) {
    if (l == r) return;
    ll mid = (l+r)/2;
    st[id].chl = New();
    st[id].chr = New();
    build(st[id].chl, l, mid);
    build(st[id].chr, mid+1, r);
  }
  void update(ll id, ll nid, ll l, ll r, ll q) {
    st[nid].val = st[id].val;
    if (l == r) {
      ++st[nid].val;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) {
      st[nid].chl = New();
      st[nid].chr = st[id].chr;
      update(st[id].chl, st[nid].chl, l, mid, q);
    }
    else {
      st[nid].chl = st[id].chl;
      st[nid].chr = New();
      update(st[id].chr, st[nid].chr, mid+1, r, q);
    }
    st[nid].val = st[st[nid].chl].val + st[st[nid].chr].val;
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (id == -1 || qr < S[l] || S[r] < ql) return 0;
    else if (ql <= S[l] && S[r] <= qr) return st[id].val;
    ll mid = (l+r)/2;
    return query(st[id].chl, l, mid, ql, qr) + query(st[id].chr, mid+1, r, ql, qr);
  }
  void Upd(ll x) {
    ll nrt = New();
    update(rt.back(), nrt, 0, ldis.size()-1, x);
    rt.push_back(nrt);
  }
}PST;

vector <ll> Z;
ll cur = 0;
void search(ll id, ll ql, ll qr, ll w) {
  if (Z.empty()) {
    rmv[id] = rt.size();
    ++rmp[rt.size()][id];
    return;
  }
  auto it = lower_bound(Z.begin(), Z.end(), ql);
  ll k = 0;
  if (it != Z.begin()) {
    it = prev(it);
    w += PST.query(rt[k], 0, ldis.size()-1, ql, qr);
    ll k = it-Z.begin()+1;
  }
  w += PST.query(rt[k], 0, ldis.size()-1, ql, qr);
  ll l = k+1, r = rt.size(), mid;
  while (l < r) {
    mid = (l+r)/2;
    auto z = PST.query(rt[mid], 0, ldis.size()-1, ql, qr);
    if (z >= w) r = mid;
    else l = mid+1;
  }
  //cout << l << " " << rt.size() << endl;
  rmv[id] = l;
  ++rmp[l][id];
}
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
	if (M == 0) return -1;
  V.push_back({0, M});
  ST.init();
  for (int i=0; i<M; ++i) {
    V.push_back({B[i], i});
    Q.push_back({B[i], 1, i});
    Q.push_back({A[i], 2, i});
  }
  B.push_back(0);
  for (int i=0; i<W; ++i) {
    ++mp[L[i]];
    Q.push_back({R[i], 3, i});
  }
  ll t = 0;
  for (auto [x, y] : mp) {
    S.push_back(x);
    mp[x] = t++;
  }
  for (auto u : L) {
    ldis.push_back(mp[u]);
  }
  sort(V.begin(), V.end());
  for (int i=0; i<M+1; ++i) G[V[i][1]] = i, VB.push_back(V[i][0]);
  sort(Q.begin(), Q.end());
  rt.push_back(PST.New());
  if (W) PST.build(rt.back(), 0, ldis.size()-1);
  for (auto [u, ty, id] : Q) {
    if (ty != 3) continue;
    Z.push_back(u);
    PST.Upd(ldis[id]);
  }
  dq[0].push_front({0, M});
  for (auto [u, ty, id] : Q) {
    if (ty == 1) {
      //cout << id << endl;
      if (dp[id] == 1e18) continue;
      //cout << X[id] << " " << Y[id] << " " << B[id] << " " << dp[id] << endl;
      while (!dq[Y[id]].empty()) {
        auto [w, z] = dq[Y[id]].back();
        if (w + T[Y[id]] * ST.query(1, 0, M, G[z]) >= dp[id]) {
          dq[Y[id]].pop_back();
          if (!dq[Y[id]].empty()) {
            rmp[rmv[dq[Y[id]].back()[1]]].erase(dq[Y[id]].back()[1]);
          }
        }
        else break;
      }
      if (!dq[Y[id]].empty()) {
        if (B[dq[Y[id]].back()[1]] == B[id]) continue;
        rb[dq[Y[id]].back()[1]] = id;
        auto y = (dp[id] - dq[Y[id]].back()[0]+T[Y[id]]-1)/T[Y[id]];
        search(dq[Y[id]].back()[1], B[dq[Y[id]].back()[1]]+1, B[id], y);
      }
      dq[Y[id]].push_back({dp[id], id});
    }
    else if (ty == 2) {
      if (!dq[X[id]].empty()) {
        auto [w, z] = dq[X[id]].front();
        dp[id] = C[id] + w + T[X[id]] * ST.query(1, 0, M, G[z]);
      }
      else dp[id] = 1e18;
    }
    else if (ty == 3) {
      auto it = lower_bound(VB.begin(), VB.end(), L[id]);
      it = prev(it);
      ST.range_update(1, 0, M, 0, it-VB.begin());
      //cout << L[id] << " " << R[id] << endl;
      ++cur;
      for (auto [id2, y] : rmp[cur]) {
        while (!dq[Y[id2]].empty()) {
          auto [w, z] = dq[Y[id2]].front();
          if (z == id2) break;
          if (!dq[Y[id2]].empty()) rmp[rmv[z]].erase(z);
          dq[Y[id2]].pop_front();
        }
        dq[Y[id2]].pop_front();
      }
    }
  }
  if (!dq[N-1].empty()) {
    auto [w, z] = dq[N-1].front();
    //cout << T[N-1] * ST.query(1, 0, M, G[z]) << endl;
    return w + T[N-1] * ST.query(1, 0, M, G[z]);
  }
  return -1;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60