Submission #940759

#	Time	Username	Problem	Language	Result	Execution time	Memory
940759		guagua0407	Harvest (JOI20_harvest)	C++17	5 / 100	5027 ms	33916 KiB

harvest

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct BIT{
    vector<int> bit;
    int n;
    BIT(int N){
        n=N;
        bit=vector<int>(n,0);
    }
    void update(int pos,int val){
        for(;pos<n;pos+=(pos&-pos)){
            bit[pos]+=val;
        }
    }
    int query(int pos){
        int ans=0;
        for(;pos>0;pos-=(pos&-pos)){
            ans+=bit[pos];
        }
        return ans;
    }
};

const int mxn=200000+5;
int a[mxn];
int b[mxn];
int nxt[mxn*2];
bool visited[mxn*2];
bool is_cycle[mxn*2];
vector<pair<int,ll>> adj[mxn*2];
int belong[mxn*2];
ll depth[mxn*2];
ll d[mxn*2];
ll sum[mxn*2];
int rev[mxn*2];
int st[mxn*2],en[mxn*2];
vector<pair<int,int>> sta;
vector<pair<int,int>> qs[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
int timer=0;

void dfs(int p,int v){
    st[v]=++timer;
    if(v>=n){
        sta.push_back({v,p});
    }
    for(auto u:adj[v]){
        if(is_cycle[u.f]) continue;
        depth[u.f]=depth[v]+u.s;
        dfs(p,u.f);
    }
    en[v]=timer;
}

int dfs_ans(int p,int v,ll t){
    if(v>=n){
        if(depth[v]-depth[p]<=t) return 1;
        else return 0;
    }
    int ans=0;
    for(auto u:adj[v]){
        ans+=dfs_ans(p,u.f,t);
    }
    return ans;
}

signed main() {_
    cin>>n>>m>>l>>c;
    ll C=c;
    c%=l;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        if(a[i]-c>=a[0]){
            nxt[i]=upper_bound(a,a+n,a[i]-c)-a-1;
            d[i]=a[i]-a[nxt[i]];
        }
        else{
            int val=(a[i]-c+l);
            nxt[i]=upper_bound(a,a+n,val)-a-1;
            d[i]=a[i]+l-a[nxt[i]];
        }
        if(d[i]==0){
            d[i]=(C+l-1)/l*l;
        }
        else{
            d[i]+=1ll*(C/l)*l;
        }
    }
    for(int i=0;i<m;i++){
        if(b[i]>=a[0]){
            nxt[i+n]=upper_bound(a,a+n,b[i])-a-1;
            d[i+n]=b[i]-a[nxt[i+n]];
        }
        else{
            int val=(b[i]+l);
            nxt[i+n]=upper_bound(a,a+n,val)-a-1;
            d[i+n]=b[i]+l-a[nxt[i+n]];
        }
    }
    for(int i=0;i<n+m;i++){
        adj[nxt[i]].push_back({i,d[i]});
    }
    vector<vector<int>> cycle;
    for(int i=0;i<n+m;i++){
        if(visited[i]) continue;
        int x=i;
        vector<int> tmp;
        while(!visited[x]){
            visited[x]=true;
            tmp.push_back(x);
            x=nxt[x];
        }
        bool ok=false;
        for(auto v:tmp){
            ok|=(v==x);
            is_cycle[v]=ok;
        }
        if(!ok) continue;
        vector<int> curcycle;
        for(auto v:tmp){
            if(is_cycle[v]){
                curcycle.push_back(v);
                belong[v]=(int)cycle.size();
            }
        }
        cycle.push_back(curcycle);
        vector<ll> dis;
        dis.push_back(0);
        for(int i=1;i<(int)curcycle.size();i++){
            dis.push_back(dis.back()+d[curcycle[i-1]]);
        }
        for(int i=0;i<(int)curcycle.size();i++){
            int prv=(i-1+(int)curcycle.size())%(int)curcycle.size();
            dis.push_back(dis.back()+d[curcycle[prv]]);
        }
        pre.push_back(dis);
    }
    for(int i=0;i<(int)cycle.size();i++){
        int cnt=0;
        for(auto v:cycle[i]){
            sta.clear();
            dfs(v,v);
            qs[i].insert(qs[i].end(),all(sta));
            sum[i]+=d[v];
            rev[v]=cnt++;
        }
    }
    int q;
    cin>>q;
    vector<pair<ll,pair<int,int>>> qys;
    vector<int> res(q);
    for(int i=0;i<q;i++){
        int v;
        ll t;
        cin>>v>>t;
        v--;
        if(!is_cycle[v]){
            //res[i]=dfs_ans(v,v,t);
            qys.push_back({t+depth[v],{i,v}});
            continue;
        }
        int id=belong[v];
        ll ans=0;
        for(auto p:qs[id]){
            ll cur=t-depth[p.f];
            if(cur<0) continue;
            ans+=cur/sum[id];
            cur%=sum[id];
            int pos=rev[p.s];
            int pos2=upper_bound(all(pre[id]),pre[id][pos]+cur)-pre[id].begin()-1;
            if((pos<=rev[v] and rev[v]<=pos2) or (pos<=rev[v]+(int)cycle[id].size() and rev[v]+(int)cycle[id].size()<=pos2)) ans++;
        }
        res[i]=ans;
    }
    for(int i=n;i<n+m;i++){
        qys.push_back({depth[i],{-1,i}});
    }
    sort(qys.begin(),qys.end());
    BIT T(mxn);
    for(auto query:qys){
        int id=query.s.f;
        int v=query.s.s;
        if(id==-1){
            T.update(st[v],1);
        }
        else{
            res[id]=T.query(en[v])-T.query(st[v]-1);
        }
    }
    for(int i=0;i<q;i++){
        cout<<res[i]<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
/*
1 1 2 5
0
1
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
*/

Compilation message (stderr)

harvest.cpp: In function 'void setIO(std::string)':
harvest.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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