Submission #1204562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204562		mychecksedad	Harvest (JOI20_harvest)	C++20	5 / 100	63 ms	17336 KiB

harvest

/* 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 = 5e5+100, M = 1e5+10, K = 52, MX = 30;


int n, m, q, loop_id[N];
ll L, C, a[N], b[N], loop_size[N];
vector<pair<ll, int>> Q[N];
ll ANS[N];
array<ll, 2> go[N];


void dfs(int v, ll dist, int loop_enter){
  if(v == loop_enter) return;
  // cerr << v << ' ' << dist << ' ' << loop_enter << '\n';
  if(loop_id[v] == 0){
    for(auto [t, idx]: Q[v]){
      if(dist <= t) ++ANS[idx];
    }
  }else{  
    for(auto [t, idx]: Q[v]){
      if(dist <= t){
        // cerr << t << ' ' << idx << 'f' << '\n';
        ANS[idx] += (t - dist) / loop_size[loop_id[v]] + 1;
      }
    }
  }
  if(loop_id[v] != 0 && loop_enter == -1)
    dfs(go[v][0], dist + go[v][1], v);
  else
    dfs(go[v][0], dist + go[v][1], loop_enter);
}

void solve(){
  cin >> n >> m >> L >> C;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    loop_id[i] = 0;
  }
  for(int i = n+1; i <= 2*n; ++i) a[i] = a[i-n] + L;
  for(int i = 1; i <= m; ++i){
    cin >> b[i];
  }
  cin >> q;
  for(int i = 1; i <= q; ++i){
    int p; cin >> p;
    ll t; cin >> t;
    Q[p].pb({t, i});
    ANS[i] = 0;
  }
  ll num = C/L, c = C%L;
  for(int i = 1; i <= n; ++i){
    int l = i+1, r = i+n, res = i+n;
    while(l <= r){
      int mid = l+r>>1;
      if(a[i + n] - a[mid] >= c){
        res = mid;
        l = mid+1;
      }else{
        r = mid-1;
      }
    }
    go[i] = {res > n ? res-n : res, num * L + a[i+n] - a[res]};
  }
  int id = 0;
  vector<bool> vis(n + 1);
  for(int i = 1; i <= n; ++i){
    if(!vis[i]){
      int v = i;
      stack<int> st;
      while(!vis[v]){
        st.push(v);
        // cerr << v << '\n';
        vis[v] = 1;
        v = go[v][0];
      }
      vi loop;
      loop.pb(v);
      while(st.size() && st.top() != v){
        loop.pb(st.top());
        st.pop();
      }
      if(st.empty() || st.top() != v){
        continue;
      }
      id++;
      loop_size[id] = 0;
      for(int x: loop){
        // cerr << x << ' ';
        loop_id[x] = id;
        loop_size[id] += go[x][1];
      }
      // en;
    }
  }
  // for(int i = 1; i <= n; ++i){
  //   cerr << go[i][0] << ' ' << go[i][1] << '\n';
  // }
  for(int i = 1; i <= m; ++i){
    int res = upper_bound(a+1, a+1+n, b[i]) - a;
    --res;
    ll d;
    if(res == 0){
      res = n; 
      d = b[i] - a[res] + L;
    }else{
      d = b[i] - a[res];
    }

    if(res == n + 1) res = 1;
    dfs(res, d, -1);
  }


  for(int i = 1; i <= q; ++i){
    cout << ANS[i] << '\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: 0 / 20
• Subtask 3: 0 / 75