Submission #1156757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156757		KhoaDuy	Harvest (JOI20_harvest)	C++17	100 / 100	445 ms	100516 KiB

harvest

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MAXN=2*1e5;
vector<vector<pair<int,int>>> graph(MAXN),grev(MAXN);
vector<int> start;
int in[MAXN],out[MAXN];
int tim=1;
int root[MAXN],dist[MAXN];
int col[MAXN];
void DFS(int u){
    col[u]=1;
    assert(graph[u].size()==1);
    int v=graph[u][0].first,w=graph[u][0].second;
    if(col[v]==1){
        start.push_back(u);
        graph[u].pop_back();
        for(int i=0;i<grev[v].size();i++){
            if(grev[v][i].first==u){
                grev[v].erase(grev[v].begin()+i);
                break;
            }
        }
        root[u]=v,dist[u]=w;
    }
    else{
        if(col[v]==0){
            DFS(v);
        }
        root[u]=root[v],dist[u]=dist[v]+w;
    }
    col[u]=2;
}
vector<vector<pair<int,int>>> group(MAXN);
struct fenwick{
    vector<int> bit;
    void build(int n){
        bit.clear(),bit.resize(0);
        bit.assign(n+1,0);
    }
    void update(int i,int x){
        assert(i<bit.size());
        for(;i<bit.size();i+=(i&(-i))){
            bit[i]+=x;
        }
    }
    int query(int i){
        assert(i>=0);
        int curr=0;
        for(;i;i-=(i&(-i))){
            curr+=bit[i];
        }
        return curr;
    }
    int range(int l,int r){
        if(l>r){
            return 0;
        }
        return (query(r)-query(l-1));
    }
};
struct que{
    int val,u,idx;
};
bool cmp(que &a,que &b){
    if(a.val!=b.val){
        return (a.val<b.val);
    }
    return (a.idx<b.idx);
}
void setup(int u){
    in[u]=tim;
    tim++;
    for(pair<int,int> &x:grev[u]){
        setup(x.first);
    }
    out[u]=tim-1;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,l,c;
    cin >> n >> m >> l >> c;
    vector<int> a(n),b(m);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        a.push_back(a[i]+l);
    }
    for(int i=0;i<m;i++){
        cin >> b[i];
    }
    int fir[m],app[m];
    for(int i=0;i<m;i++){
        int pos=upper_bound(a.begin(),a.end(),b[i])-a.begin();
        pos--;
        if(pos>=0){
            fir[i]=pos;
            app[i]=b[i]-a[pos];
        }
        else{
            assert(pos==-1);
            fir[i]=n-1;
            app[i]=l-a[n-1]+b[i];
        }
    }
    for(int i=0;i<n;i++){
        int j=lower_bound(a.begin(),a.end(),a[i]+(c%l))-a.begin();
        for(;j<a.size()&&a[j]-a[i+1]<(c%l);j++){
            graph[j%n].push_back({i,a[j]-a[i]+c-(c%l)});
            grev[i].push_back({j%n,a[j]-a[i]+c-(c%l)});
        }
    }
    for(int i=0;i<n;i++){
        if(col[i]==0){
            DFS(i);
        }
    }
    int q;
    cin >> q;
    int ans[q]={0};
    vector<que> queri(q);
    for(int i=0;i<q;i++){
        int v,t;
        cin >> v >> t;
        v--;
        group[v].push_back({t,i});
        queri[i]={t+dist[v],v,i};
    }
    for(int i=0;i<m;i++){
        queri.push_back({app[i]+dist[fir[i]],fir[i],-1});
    }
    sort(queri.begin(),queri.end(),cmp);
    for(int r:start){
        setup(r);
    }
    fenwick bit;
    bit.build(tim-1);
    for(que &x:queri){
        if(x.idx==-1){
            bit.update(in[x.u],1);
        }
        else{
            ans[x.idx]+=bit.range(in[x.u],out[x.u]);
        }
    }
    vector<vector<int>> source(n);
    for(int i=0;i<m;i++){
        source[root[fir[i]]].push_back(app[i]+dist[fir[i]]);
    }
    for(int s=0;s<n;s++){
        if(root[s]!=s){
            continue;
        }
        queri.clear();
        queri.resize(0);
        int d=dist[s];
        int u=s;
        while(true){
            for(pair<int,int> &x:group[u]){
                if(x.first-(d-dist[u])<0){
                    continue;
                }
                queri.push_back({x.first-(d-dist[u]),-1,x.second});
            }
            if(graph[u].size()==0){
                break;
            }
            u=graph[u][0].first;
        }
        for(int t:source[s]){
            queri.push_back({t,-1,-1});
        }
        sort(queri.begin(),queri.end(),cmp);
        map<int,int> mp;
        int idx=1;
        for(que &x:queri){
            mp[x.val%d]=1;
        }
        for(pair<const int,int> &x:mp){
            x.second=idx;
            idx++;
        }
        bit.build(idx-1);
        int sum=0;
        for(que &x:queri){
            int pos=mp[x.val%d];
            if(x.idx==-1){
                sum+=(x.val/d);
                bit.update(pos,1);
            }
            else{
                ans[x.idx]-=sum;
                ans[x.idx]+=(((x.val/d)+1)*bit.range(1,idx-1));
                ans[x.idx]-=bit.range(pos+1,idx-1);
            }
        }
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << endl;
    }
}

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