Submission #1204941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204941		mychecksedad	Tower (JOI24_tower)	C++20	100 / 100	637 ms	49764 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e6+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e13;

int n, q, m;
ll D, A, B;
array<ll, 2> P[N], U[N];
vector<pair<ll, int>> Q;
vector<ll> ANS, VAL;
set<pair<ll, ll>> S;
ll T[N];
bool lazy[N]; // ate a delete query


int POS(ll x){
  return lower_bound(all(VAL), x) - VAL.begin() + 1;
}

int POS_R(ll x){
  int pos = lower_bound(all(VAL), x) - VAL.begin() + 1;
  if(pos == VAL.size() + 1 || VAL[pos - 1] > x) --pos;
  return pos;
}

void build(int l, int r, int k){
  T[k] = -1;
  lazy[k] = false;
  if(l == r){
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1);
  build(mid+1, r, k<<1|1);
}

void push(int k){
  if(T[k] == -1) return;
  if(T[k] == -2){
    lazy[k<<1] = lazy[k<<1|1] = false;
    T[k<<1] = T[k];
    T[k<<1|1] = T[k];
  }else{
    if(lazy[k]){
      T[k<<1] = T[k];
      T[k<<1|1] = T[k];
      lazy[k<<1] = lazy[k<<1|1] = true;
      lazy[k] = false;
    }else{
      if(T[k<<1] < 0){
        if(T[k<<1] == -2) lazy[k<<1] = true;
        T[k<<1] = T[k];
      }
      if(T[k<<1|1] < 0){
        if(T[k<<1|1] == -2) lazy[k<<1|1] = true;
        T[k<<1|1] = T[k];
      }
    }
  }
  T[k] = -1;
}

void upd(int l, int r, int ql, int qr, int k, ll val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    // cerr << l << ' ' << r << ' ' << val << '\n';
    if(val == -1){
      T[k] = -2; // erase
      lazy[k] = false;
    }else{
      if(T[k] == -1 || T[k] == -2){
        if(T[k] == -2){
          lazy[k] = true;
        }else{
          lazy[k] = false;
        }
        T[k] = val;
      }
    }
    return;
  }
  int mid = l+r>>1;
  push(k);
  upd(l, mid, ql, qr, k<<1, val);
  upd(mid+1, r, ql, qr, k<<1|1, val);
}

ll get(int l, int r, int p, int k){
  // cerr << l << ' ' << r << ' ' << p << ' ' << T[k] << endl;
  if(l == r){
    return T[k];
  }
  push(k);
  int mid = l+r>>1;
  if(p <= mid) return get(l, mid, p, k<<1);
  return get(mid+1, r, p, k<<1|1);
}


void add(ll l, ll r, ll d_val){
  r = min(r, l + D - 1);
  l %= D;
  r %= D;
  // cerr << "add: " << l << ' ' << r << endl;
  if(l <= r){
    int lpos = POS(l), rpos = POS_R(r);
    if(lpos <= rpos){
      upd(1, m, lpos, rpos, 1, d_val);
    }
  }else{
    int lpos = POS(l), rpos = POS_R(D-1);
    int lpos2 = POS(0), rpos2 = POS_R(r);
    if(lpos <= rpos){
      upd(1, m, lpos, rpos, 1, d_val);
    }
    if(lpos2 <= rpos2){
      upd(1, m, lpos2, rpos2, 1, d_val + 1);
    }
  }
}

void del(ll l, ll r){
  r = min(r, l + D - 1);
  l %= D;
  r %= D;
  // cerr << "del: " << l << ' ' << r << endl;
  if(l <= r){
    int lpos = POS(l), rpos = POS_R(r);
    if(lpos <= rpos){
      upd(1, m, lpos, rpos, 1, -1);
    }
  }else{
    int lpos = POS(l), rpos = POS_R(D-1);
    int lpos2 = POS(0), rpos2 = POS_R(r);
    if(lpos <= rpos){
      upd(1, m, lpos, rpos, 1, -1);
    }
    if(lpos2 <= rpos2){
      upd(1, m, lpos2, rpos2, 1, -1);
    }
  }
} 


ll calc(ll p, map<ll, ll> &dp){
  // cerr << "calc: " << p << '\n';
  // we want p % D
  ll last_v = get(1, m, POS(p % D), 1) * D + (p % D); // seg tree only stores / D
  // cerr << "last_v: " << last_v << '\n';
  auto it = S.lower_bound(pair<ll, ll>{last_v - D, INF});
  if(it == S.begin()){
    return (p-last_v)/D * B + last_v * A;
  }
  it = prev(it);
  ll last_r = (*it).ss;
  // cerr << "lsat_r : " << last_r << '\n';
  return ((p-last_v)/D)*B + (last_v - (last_r + D)) * A + dp[last_r] + B;
}


void solve(){
  cin >> n >> q >> D >> A >> B;
  for(int i = 1; i <= n; ++i){
    cin >> P[i][0] >> P[i][1];
  }
  Q.resize(q);
  ANS.resize(q);
  for(int i = 1; i <= q; ++i){
    cin >> Q[i-1].ff;
    Q[i-1].ss=i-1;
    VAL.pb(Q[i-1].ff % D);
  }
  sort(P+1, P+1+n);

  ll lst = 0;
  for(int i = 1; i <= n; ++i){
    U[i] = {lst, P[i][0] - 1};
    lst = P[i][1] + 1;
  }
  U[n + 1] = array<ll, 2>{lst, INF-1};

  S.insert(pair<ll,ll>{U[1][0], U[1][1]});
  for(int i = 2; i <= n + 1; ++i){
    auto it = S.lower_bound(pair<ll,ll>{U[i][0] - D, INF});
    ll last_av = -1;
    if(it == S.begin() || prev(it)->second < U[i][0] - D){
      if(it != S.end()){
        last_av = it->first + D;
      }else{
        last_av = INF;
      }
    } else{
      last_av = U[i][0];
    }
    if(last_av <= U[i][1]){
      S.insert({last_av, U[i][1]});
    }
  }
  for(auto [x, y]: S) VAL.pb(y%D);
  if(A * D <= B){
    map<ll, ll> dp;
    dp[0] = 0;
    for(auto [l, r]: S){
      if(l == 0) continue;
      auto it = S.lower_bound(pair<ll,ll>{l-D, INF});
      it = prev(it);
      ll L = it->first;
      dp[l] = dp[L] + (l - D - L) * A + B;
    }
    for(int i = 1; i <= q; ++i){
      ll X = Q[i - 1].ff;
      auto it = S.lower_bound(pair<ll,ll>{X, INF});
      if(it == S.begin() || (prev(it)->second < X)){
        cout << "-1\n";
      }else{
        cout << dp[prev(it)->ff] + (X - prev(it)->ff) * A << '\n';
      } 
    }
    return;
  }

  sort(all(VAL));
  VAL.erase(unique(all(VAL)), VAL.end());

  m = VAL.size();
  build(1, m, 1);

  // for(auto [x,y]: S) cerr << x << ' '<< y << '\n';
  //   return;

  sort(all(Q));

  map<ll, ll> dp;
  dp[0] = 0;

  auto it = S.begin();
  add((*it).ff, (*it).ss, 0ll);
  ll R = (*it).ss;
  dp[R] = R/D * B + (R%D) * A;

  // cerr << R << ' ' << dp[R] << '\n';

  for(int i = 1; i <= q; ++i){
    ll X = Q[i - 1].ff;
    while(next(it) != S.end() && (*next(it)).ff <= X){
      it = next(it);
      del(R + 1, (*it).ff - 1);
      add((*it).ff, (*it).ss, (*it).ff/D);
      R = (*it).ss;
      dp[R] = calc(R, dp);
      // cerr << R << ' ' << dp[R] << '\n';
    }
    if((*it).ss < X){
      ANS[Q[i - 1].ss] = -1;
    }else{
      ANS[Q[i - 1].ss] = calc(X, dp);
    }
  }
  for(int i = 1; i <= q; ++i){
    cout << ANS[i-1] << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• Subtask 1: 5 / 5
• Subtask 2: 38 / 38
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32