Submission #946322

#	Time	Username	Problem	Language	Result	Execution time	Memory
946322		guagua0407	Harvest (JOI20_harvest)	C++17	100 / 100	410 ms	158188 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=400000+5;
const int inf=1e18;
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>> js[mxn];
vector<pair<pair<int,int>,int>> is[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
int timer=0;

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

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++){
        int pos=upper_bound(a,a+n,(a[i]-c+l)%l)-a-1;
        if(pos==-1) pos=n-1;
        nxt[i]=pos;
        d[i]=((a[i]-c+l)%l-a[pos]+l)%l+C;
    }
    for(int i=0;i<m;i++){
        int pos=upper_bound(a,a+n,b[i])-a-1;
        if(pos==-1) pos=n-1;
        nxt[i+n]=pos;
        d[i+n]=(b[i]-a[pos]+l)%l;
    }
    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]]);
        }
        pre.push_back(dis);
        for(int i=0;i<(int)curcycle.size();i++){
            rev[curcycle[i]]=i;
        }
    }
    for(int i=0;i<(int)cycle.size();i++){
        int cnt=0;
        for(auto v:cycle[i]){
            sta.clear();
            dfs(i,v,v);
            js[i].insert(js[i].end(),all(sta));
            sum[i]+=d[v];
        }
    }
    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]){
            qys.push_back({t+depth[v],{i,v}});
            continue;
        }
        int id=belong[v];
        is[id].push_back({{t-pre[id][rev[v]],v},i});
    }
    // tree
    {
        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]);
            }
        }
    }
    // cycle
    for(int t=0;t<(int)cycle.size();t++){
        {
            vector<pair<pair<int,int>,int>> vec;
            vector<int> xs;
            xs.push_back(-inf);
            for(auto v:is[t]){
                int a=v.f.f/sum[t];
                assert(sum[t]!=0);
                if(a*sum[t]>v.f.f) a--;
                int b=v.f.f-a*sum[t];
                xs.push_back(b);
                vec.push_back({{a,v.s},b});
            }
            for(auto v:js[t]){
                int a=v.f/sum[t];
                assert(sum[t]!=0);
                if(a*sum[t]>v.f) a--;
                int b=v.f-a*sum[t];
                xs.push_back(b);
                vec.push_back({{a,-1},b});
            }
            sort(all(xs));
            xs.resize(unique(all(xs))-xs.begin());
            sort(all(vec));
            int sum2=0;
            int cnt=0;
            BIT T(xs.size());
            for(auto v:vec){
                int pos=lower_bound(all(xs),v.s)-xs.begin();
                if(v.f.s==-1){
                    sum2+=v.f.f;
                    cnt++;
                    T.update(pos,1);
                }
                else{
                    int i=v.f.s;
                    res[i]+=cnt*v.f.f;
                    res[i]-=sum2;
                    res[i]+=T.query(pos);
                }
            }
        }
        {
            vector<pair<pair<int,int>,int>> vec;
            vector<int> xs;
            xs.push_back(-inf);
            for(auto v:is[t]){
                xs.push_back(v.f.f);
                vec.push_back({{rev[v.f.s],v.s},v.f.f});
            }
            for(auto v:js[t]){
                xs.push_back(v.f);
                vec.push_back({{rev[v.s],-1},v.f});
            }
            sort(all(xs));
            xs.resize(unique(all(xs))-xs.begin());
            sort(all(vec));
            reverse(all(vec));
            BIT T(xs.size());
            for(auto v:vec){
                int pos=lower_bound(all(xs),v.s)-xs.begin();
                if(v.f.s==-1){
                    T.update(pos,1);
                }
                else{
                    int i=v.f.s;
                    res[i]-=T.query(pos);
                }
            }
        }
    }
    for(int i=0;i<q;i++){
        //assert(res[i]>=0);
        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 'int main()':
harvest.cpp:135:13: warning: unused variable 'cnt' [-Wunused-variable]
  135 |         int cnt=0;
      |             ^~~
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: 20 / 20
• Subtask 3: 75 / 75