제출 #1049845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049845		hotboy2703	수확 (JOI20_harvest)	C++17	100 / 100	184 ms	91280 KiB

harvest

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
struct BIT{
    vector <ll> val;
    ll n;
    void init(ll N){
        n=N;
        val.resize(n+1);
    }    
    void upd(ll i,ll v){
        for (;i <= n;i += i &-i)val[i]+=v;
    }
    ll get(ll i){
        ll res = 0;
        for (;i > 0;i -= i &-i)res+=val[i];
        return res;
    }
    ll query(ll l,ll r){
        return get(r)-get(l-1);
    }
};
ll n,m,L,C;
ll p[MAXN],dist[MAXN];
bool cycle[MAXN];
ll in[MAXN];
pll c[MAXN];
ll a[MAXN],b[MAXN];
ll out[MAXN],timeDFS;
ll cycle_id[MAXN];
ll sz[MAXN];
BIT s[MAXN];
BIT s2[MAXN];
ll cnt[MAXN];
ll pre[MAXN];
ll dist_root[MAXN];
ll cycle_length[MAXN];
vector <ll> all_md[MAXN];
ll cycle_root[MAXN];
ll ans[MAXN];
ll root[MAXN];
vector <ll> g[MAXN];
void dfs(ll u){
    in[u] = ++timeDFS;
    for (auto v:g[u]){
        dist[v] += dist[u];
        root[v] = root[u];
        dfs(v);
    }
    out[u] = timeDFS;
}
struct query{
    ll t,v,id;
};

int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m>>L>>C;
    for (ll i = 1;i <= n;i ++)cin>>a[i];
    for (ll i = 1;i <= m;i ++)cin>>b[i];
    for (ll i = 1;i <= n;i ++){
        ll r = a[i] - C;
        ll md = (r % L + L) % L;
        auto tmp = upper_bound(a+1,a+1+n,md)-a;
        tmp--;
        if (tmp==0)tmp=n;
        p[i] = tmp;
        dist[i] = C + (md - a[tmp] + L)%L;
        // cout<<i<<' '<<p[i]<<' '<<dist[i]<<endl;
    }
    for (ll i = 1;i <= n;i ++){
        if (!in[i]){
            ll cur = i;
            vector <ll> all;
            while (!in[cur]){
                all.push_back(cur);
                in[cur] = 1;
                cur = p[cur];
            }
            if (in[cur] == 1){
                for (ll j = 0;j < sz(all);j ++){
                    if (all[j] == cur){
                        for (ll k = j;k < sz(all);k ++){
                            cycle[all[k]] = 1;
                            sz[cur]++;
                            cycle_root[all[k]] = cur;
                            dist_root[all[k]] = cycle_length[cur];
                            cycle_length[cur] += dist[all[k]];
                            cycle_id[all[k]] = k-j+1;
                        }
                        s[cur].init(sz[cur]);
                        for (ll k = 0;k < j;k ++)g[all[k+1]].push_back(all[k]);
                        break;
                    }
                }
            }
            else{
                all.push_back(cur);
                for (ll j = 0;j + 1 < sz(all);j ++){
                    g[all[j+1]].push_back(all[j]);
                }
            }
            for (auto x:all)in[x] = 2;
        }
    }
    for (ll i = 1;i <= n;i ++){
        if (cycle[i]){root[i] = i;dist[i] = 0;dfs(i);}
    }
    // cout<<"SUS "<<dist[n]<<endl;
    for (ll i = 1,ptr = 1;i <= m;i ++){
        while (ptr <= n && a[ptr] <= b[i])ptr++;
        if (ptr==1)c[i].se = n;
        else c[i].se = ptr-1;
        c[i].fi = dist[c[i].se] + (b[i] - a[c[i].se] + L) % L;
        // cout<<c[i].fi<<' '<<c[i].se<<'\n';
    }
    ll q;
    cin>>q;
    vector <query> a1,a2;
    for (ll i = 1;i <= q;i ++){
        ll t,v;
        cin>>v>>t;
        if (cycle[v]){
            a1.push_back({t,v,i});
        }
        else{
            a2.push_back({t,v,i});
        }
    }
    sort(a2.begin(),a2.end(),[](query x,query y){return x.t+dist[x.v] < y.t + dist[y.v];});
    sort(c+1,c+1+m);
    {
        BIT tmp;
        tmp.init(n);
        for (ll i = 0,ptr = 1;i < sz(a2);i ++){
            // cout<<i<<endl;
            while (ptr<=m && c[ptr].fi <= a2[i].t + dist[a2[i].v]){
                tmp.upd(in[c[ptr].se],1);
                ptr++;
            }
            ans[a2[i].id] = tmp.query(in[a2[i].v],out[a2[i].v]);
        }
    }
    vector <pll> rem;
    vector <pll> in_cycle;
    for (ll i = 1;i <= m;i ++){
        // cout<<i<<endl;
        ll r = cycle_root[root[c[i].se]];
        pll tmp = MP(c[i].fi + cycle_length[r] - dist_root[root[c[i].se]],root[c[i].se]);
        // cout<<tmp.fi<<' '<<tmp.se<<'\n';
        in_cycle.push_back(tmp);
        all_md[r].push_back(tmp.fi % cycle_length[r]);
        rem.push_back(MP(c[i].fi-dist_root[tmp.se],tmp.se));
    }
    // return 0;
    for (ll i =1 ;i <= n;i ++){
        if (i == cycle_root[i]){
            sort(all_md[i].begin(),all_md[i].end());
            all_md[i].resize(unique(all_md[i].begin(),all_md[i].end())-all_md[i].begin());
            s2[i].init(sz(all_md[i]));
        }
    }
    sort(rem.begin(),rem.end());
    sort(in_cycle.begin(),in_cycle.end());
    sort(a1.begin(),a1.end(),[](query x,query y){return x.t - dist_root[x.v] < y.t - dist_root[y.v];});
    // for (ll i = 1;i <= n;i ++){
    //     cout<<i<<' '<<cycle[i]<<' '<<cycle_root[i]<<endl;
    // }
    for (ll i = 0,ptr = 0,ptr2 = 0;i < sz(a1);i ++){
        // cout<<i<<endl;
        while (ptr < sz(rem) && rem[ptr].fi <= a1[i].t - dist_root[a1[i].v]){
            // cout<<rem[ptr].se<<' '<<ptr<<endl;
            s[cycle_root[rem[ptr].se]].upd(cycle_id[rem[ptr].se],1);
            ptr++;
        }
        while (ptr2 < sz(in_cycle) && in_cycle[ptr2].fi <= a1[i].t-dist_root[a1[i].v]){
            ll r = cycle_root[in_cycle[ptr2].se];
            cnt[r]++;
            pre[r] -= in_cycle[ptr2].fi / cycle_length[r];
            s2[r].upd(lower_bound(all_md[r].begin(),all_md[r].end(),in_cycle[ptr2].fi%cycle_length[r]) - all_md[r].begin() + 1, +1);
            ptr2++;
        }
        ll r = cycle_root[a1[i].v];
        // cout<<i<<' '<<a1[i].v<<' '<<r<<' '<<cycle_length[r]<<' '<<sz(s[r].val)<<' '<<pre[r]<<endl;
        ll res = (a1[i].t-dist_root[a1[i].v]) / cycle_length[r] * cnt[r] + pre[r]
                +s2[r].get(upper_bound(all_md[r].begin(),all_md[r].end(),(a1[i].t-dist_root[a1[i].v]) % cycle_length[r])-all_md[r].begin())
                +s[r].get(cycle_id[a1[i].v]);
        ans[a1[i].id] = res;
    }
    for (ll i = 1;i <= q;i ++)cout<<ans[i]<<'\n';
}

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