Submission #1205895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205895		mychecksedad	Harvest (JOI20_harvest)	C++20	0 / 100	102 ms	93608 KiB

harvest

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#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;
typedef tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, tree_order_statistics_node_update> oset;

int n, m, q, loop_id[N], cnt = 0;
ll L, C, a[N], b[N], cycle_size[N];
vector<pair<ll, int>> Q[N];
ll ANS[N];
array<ll, 2> go[N];
vector<pair<int, ll>> g[N];
vector<ll> G[N];
oset T[N];

vector<bool> vis;
int st;
void dfs(int v, ll dep){
  vis[v] = 1;
  // cerr << v << " dfs\n";
  int big = -1; 
  for(auto [u, w]: g[v]){
    if(u == st) continue;
    dfs(u, dep + w);
    if(big == -1 || T[u].size() > T[big].size()) big = u;
  }
  if(big != -1){
    T[v].swap(T[big]);
  }
  for(ll x: G[v]) T[v].insert({x + dep, cnt++});
  for(auto [u, w]: g[v]){
    if(u != big && u != st){
      for(auto x: T[u]) T[v].insert(x);
      T[u].clear();
    }
  }
  for(auto [t, idx]: Q[v]){
    int num = T[v].order_of_key(pair<ll, int>{t + dep + 1, -1});
    ANS[idx] = num;
  }
}


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;
  vis.resize(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++;
      cycle_size[id] = 0;
      for(int x: loop){
        loop_id[x] = id;
        cycle_size[id] += go[x][1];
      }
    }
  }

  for(int i = 1; i <= n; ++i){
    g[go[i][0]].pb({i, go[i][1]});
  }

  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;
    G[res].pb(d);
    // cerr << res << ' ' << d << '\n';
  }
  // en;
  // for(int i = 1; i <= n; ++i){
  //   cerr << go[i][0] << ' ' << go[i][1] << '\n';
  // }
  // en;
  vis.clear();
  vis.resize(n + 1);
  for(int i = 1; i <= n; ++i){
    if(loop_id[i] && !vis[i]){
      st = i;
      dfs(i, 0ll);
      // we managed to carry all apples to the vertex i, now we need to handle queries in loop vertices (the periodic handouts)
    }
  }
  vis.clear();
  vis.resize(n + 1);

  for(int i = 1; i <= n; ++i){
    if(loop_id[i] == 0 || vis[i]) continue;
    vector<array<ll, 2>> QQ; // queries fixed at V
    ll dst = 0;
    ll SZ = cycle_size[loop_id[i]];
    int V = i;

    for(int x = V; !vis[x]; x = go[x][0]){
      for(auto [t, idx]: Q[x]){
        QQ.pb({t - (dst == 0 ? SZ : dst), idx});
      }      
      vis[x] = 1;
      dst += go[x][1];
    }
    oset MD; // contains modulo SZ's

    sort(all(QQ));

    ll sum = 0;
    int ptr = 0;
    auto it = T[i].begin();

    // for(auto [t, idx]: QQ){
    //   while(it != T[i].end() && (*it).ff <= t){
    //     MD.insert({((*it).ff + SZ) % SZ, ptr});
    //     sum += - ((*it).ff / SZ);
    //     ++ptr;
    //     ++it;
    //   }
    //   ANS[idx] += ptr * (t / SZ) + sum + (MD.order_of_key(pair<ll, int>{((t + SZ) % SZ) + 1, -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: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75