Submission #1006266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006266		Unforgettablepl	Harvest (JOI20_harvest)	C++17	100 / 100	438 ms	108884 KiB

harvest

#include <bits/stdc++.h>
using namespace std;


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<long long,long long>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;

#define int long long

const int INF = 1e18;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,l,c;
    cin >> n >> m >> l >> c;
    vector<int> employee(n+1);
    vector<int> apple(m);
    vector<pair<int,int>> adj(n+1);
    vector<vector<int>> revadj(n+1);
    for(int i=1;i<=n;i++)cin>>employee[i];
    for(int&i:apple)cin>>i;
    for(int i=1;i<=n;i++){
        int modded = c%l;
        int iter = 0;
        for(int jump=131072;jump;jump/=2){
            if(iter+jump>n)continue;
            if((l+employee[i]-employee[(n-iter-jump+i)%n +1])%l < modded)iter+=jump;
        }
        iter++;
        if(iter==n+1){
            adj[i] = {i,(c/l)*l + l};
            continue;
        }
        adj[i] = {(n-iter+i)%n +1,(c/l)*l + (l+employee[i]-employee[(n-iter+i)%n +1])%l};
        revadj[adj[i].first].emplace_back(i);
    }
    vector<int> depth(n+1);
    vector<bool> visited(n+1);
    vector<int> heads;
    function<void (int)> front_dfs = [&](int x){
        if(visited[x])return;
        visited[x]=true;
        front_dfs(adj[x].first);
        if(depth[adj[x].first]==0)heads.emplace_back(x);
        depth[x] = depth[adj[x].first]+adj[x].second;
    };
    for(int i=1;i<=n;i++)if(!visited[i])front_dfs(i);
    vector<vector<int>> apples(n+1);
    vector<vector<pair<int,int>>> queries(n+1);
    for(int&i:apple){
        int start = -1;
        if(i<employee[1])start = n;
        else {
            start = upper_bound(employee.begin()+1,employee.end(),i)-employee.begin()-1;
        }
        apples[start].emplace_back((l+i-employee[start])%l);
    }
    int q;
    cin >> q;
    vector<int> ans(q+1);
    for(int i=1;i<=q;i++){
        int v,t;
        cin >> v >> t;
        queries[v].emplace_back(t,i);
    }
    visited = vector<bool>(n+1);
    int uid = 0;
    function<orderedset(int)> calc_linear_dfs = [&](int x){
        // cout << x << endl;
        orderedset curr;
        if(visited[x])return curr;
        visited[x] = true;
        for(int&i:revadj[x]){
            auto t = calc_linear_dfs(i);
            if(curr.size()<t.size())curr.swap(t);
            for(auto j:t)curr.insert(j);
        }
        for(int&i:apples[x])curr.insert({i+depth[x],++uid});
        for(auto[t,idx]:queries[x]){
            ans[idx] = curr.order_of_key({t+depth[x],INF});
        }
        return curr;
    };
    for(int&i:heads){
        auto t = calc_linear_dfs(i);
        orderedset curr;
        int cycle_len = depth[adj[i].first];
        int offset = 0;
        for(auto [x,y]:t)curr.insert({(x-adj[i].second)%cycle_len,y});
        for(auto [x,y]:t)offset-=(x-adj[i].second)/cycle_len;
        function<void(int,int)> calc = [&](int x,int len){
            for(auto[t,idx]:queries[x]){
                t-=len;
                if(t<0)continue;
                ans[idx]+=curr.size()*(t/cycle_len);
                t%=cycle_len;
                ans[idx]+=curr.order_of_key({t,INF});
                ans[idx]+=offset;
            }
            if(x==i)return;
            calc(adj[x].first,len+adj[x].second);
        };
        calc(adj[i].first,adj[i].second);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75