Submission #1105063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105063		VinhLuu	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	2059 ms	71624 KiB

Main

#include <bits/stdc++.h>
//#define int long long
#define ll long long
using namespace std;

const int N = 1e6 + 5;
const int oo = 1e9;

int n, m, k, q, a[N], b[N], _s[N], _t[N];

int le[N], ri[N], f[N];

int st[2][N << 2];

void build(int i,int l,int r){
  if(l == r){
    st[0][i] = st[1][i] = l;
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1|1, mid + 1, r);
  st[0][i] = n + 1;
  st[1][i] = 0;
}

void dolz(int i){
  if(st[0][i] != n + 1){
    int x = st[0][i]; st[0][i] = n + 1;
    st[0][i << 1] = min(st[0][i << 1], x);
    st[0][i << 1|1] = min(st[0][i << 1|1], x);
  }
  if(st[1][i] != 0){
    int x = st[1][i]; st[1][i] = 0;
    st[1][i << 1] = max(st[1][i << 1], x);
    st[1][i << 1|1] = max(st[1][i << 1|1], x);
  }
}

void update(int i,int l,int r,int u,int v,int val,int type){
  if(l > r || r < u || v < l) return;
  if(u <= l && r <= v){
    if(!type) st[0][i] = min(st[0][i], val);
    else st[1][i] = max(st[1][i], val);
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, v, val, type);
  update(i << 1|1, mid + 1, r, u, v, val, type);
}

void done(int i,int l,int r){
  if(l == r){
    le[l] = st[0][i];
    ri[l] = st[1][i];
    return;
  }
  dolz(i);
  int mid = (l + r) / 2;
  done(i << 1, l, mid);
  done(i << 1|1, mid + 1, r);
}

void pre(){
  build(1, 1, n);
  for(int i = 1; i <= m; i ++){
    if(a[i] < b[i]){
      update(1, 1, n, a[i], min(a[i] + k - 1, b[i] - 1), b[i], 1);
    }else update(1, 1, n, max(a[i] - k + 1, b[i] + 1), a[i], b[i], 0);
  }
  done(1, 1, n);
}

namespace sub3{
  int f[N];
  void solve(){
    pre();

    for(int k = 1; k <= q; k ++){
      int x = _s[k], y = _t[k];
      queue<int> q;
      for(int i = 1; i <= n; i ++) f[i] = oo;
      for(int i = le[x]; i <= ri[x]; i ++){
        f[i] = 1;
        q.push(i);
      }
      int pl = le[x], pr = ri[x];
      f[x] = 0;
      while(!q.empty()){
        int u = q.front(); q.pop();
        if(le[u] < pl){
          for(int i = le[u]; i <= pl - 1; i ++){
            f[i] = f[u] + 1;
            q.push(i);
          }
          pl = le[u];
        }
        if(ri[u] > pr){
          for(int i = pr + 1; i <= ri[u]; i ++){
            f[i] = f[u] + 1;
            q.push(i);
          }
          pr = ri[u];
        }
      }
      if(f[y] == oo){
        cout << -1 << "\n";
        continue;
      }else cout << f[y] << "\n";
    }
  }
}

namespace sub5{
  int kq[N];
  vector<int> Q[N];

  struct DATA{
    int T[N << 2], lz[N << 2], sum[N << 2];

    void add(int &x,int y){
      if(x == oo) return;
      x += y;
    }

    void init(int i,int l,int r){
      if(l == r){
        T[i] = oo;
        lz[i] = -1;
        return;
      }
      int mid = (l + r) / 2;
      init(i << 1, l, mid);
      init(i << 1|1, mid + 1, r);
      lz[i] = -1;
      T[i] = oo;
    }

    void lazy(int i){
      if(lz[i] != -1){
        int x = lz[i]; lz[i] = -1;

        lz[i << 1] = lz[i << 1|1] = x;
        sum[i << 1] = sum[i << 1|1] = 0;
        T[i << 1] = T[i << 1|1] = x;
      }
      if(sum[i] != 0){
        int x = sum[i]; sum[i] = 0;
        if(lz[i << 1] != -1){
          lz[i << 1] += x;
          add(T[i << 1], x);
        }else{
          add(T[i << 1], x);
          sum[i << 1] += x;
        }
        if(lz[i << 1|1] != -1){
          lz[i << 1|1] += x;
          add(T[i << 1|1], x);
        }else{
          add(T[i << 1|1], x);
          sum[i << 1|1] += x;
        }
      }
    }

    void alter(int i,int l,int r,int u,int v,int val){
      if(l > r || r < u || v < l) return;
      if(u <= l && r <= v){
        T[i] = val;
        lz[i] = val;
        sum[i] = 0;
        return;
      }
      lazy(i);
      int mid = (l + r) / 2;
      alter(i << 1, l, mid, u, v, val);
      alter(i << 1|1, mid + 1, r, u, v, val);
    }

    void change(int i,int l,int r,int u,int v,int val){
      if(l > r || r < u || v < l) return;
      if(u <= l && r <= v){
        if(lz[i] != -1){
          add(T[i], val);
          lz[i] += val;
        }else{
          add(T[i], val);
          sum[i] += val;
        }
        return;
      }
      lazy(i);
      int mid = (l + r) / 2;
      change(i << 1, l, mid, u, v, val);
      change(i << 1|1, mid + 1, r, u, v, val);
    }

    int query(int i,int l,int r,int u){
      if(l > r || r < u || u < l) return 0;
      if(l == r){
        return T[i];
      }
      lazy(i);
      int mid = (l + r) / 2;
      return query(i << 1, l, mid, u) + query(i << 1|1, mid + 1, r, u);
    }
  } tree;

  int cn[N];

  void solve(){
    pre();
    for(int i = 1; i <= q; i ++) Q[_s[i]].push_back(i);
    stack<pair<int,int>> sk;
    tree.init(1, 1, n);
    for(int i = n; i >= 1; i --){
      vector<pair<int,int>> vr;
      cn[i] = ri[i];
      cerr << i << " " << ri[i] << " h\n";
      while(!sk.empty() && sk.top().first <= ri[i]){
        cerr << sk.top().first << " " << sk.top().second << " kj\n";
        vr.push_back({sk.top().first, sk.top().second});
        cn[i] = max(cn[i], cn[sk.top().first]);
        sk.pop();
      }

      cerr << i << " " << ri[i] << " " << cn[i] << " change\n";

      tree.alter(1, 1, n, i, ri[i], 1);
//      cerr << tree.query(1, 1, n, 4) << " rk\n";

      if(vr.empty()){
        tree.change(1, 1, n, ri[i] + 1, n, 1);
      }else{
        int cnt = (int)vr.size();
        cerr << vr[0].first << " " << vr[0].second << " " << cnt << " check\n";
        if(vr[0].second > ri[i]){
          cn[ri[i] + 1] = cn[vr[0].first];
          sk.push({ri[i] + 1, vr[0].second});
          cnt--;
        }
        tree.change(1, 1, n, ri[i] + 1, n, 1 - cnt);
      }
      for(auto j : Q[i]){
        if(cn[i] < _t[j]) kq[j] = oo;
        else kq[j] = tree.query(1, 1, n, _t[j]);
      }

      sk.push({i, ri[i]});
    }

    for(int i = 1; i <= q; i ++){
      if(kq[i] == oo) cout << -1 << "\n";
      else cout << kq[i] << "\n";
    }
  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n >> k >> m;
  for(int i = 1; i <= m; i ++) cin >> a[i] >> b[i];
  cin >> q;
  for(int i = 1; i <= q; i ++) cin >> _s[i] >> _t[i];
  sub5 :: solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:264:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:265:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13