Submission #1094303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094303		vjudge1	Harvest (JOI20_harvest)	C++17	5 / 100	132 ms	60432 KiB

harvest

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll

typedef long long ll;
typedef pair<int,int> pii;

const ll maxn = 4e5 + 69;
const ll mod  = 1e9 + 7;
const ll inf  = 1e18;

int n,m,l,c,a[maxn],b[maxn],q;
int in[maxn],out[maxn],Time,cnt;
bool vis[maxn],cycle[maxn];
int st[maxn];
int w[maxn],id[maxn],sum[maxn];
vector<int> adj[maxn],nen[maxn],L[maxn],Q;
int dep[maxn],deg[maxn],up[maxn],res[maxn];
struct qr
{
    int id,u,v,w;
    bool operator <(const qr& o) const
    {
        return make_pair(w,id) < make_pair(o.w,o.id) ;
    }
};
vector<qr> query1,query2[maxn];

void Update(int u,int v)
{
    for(;u<=4e5;u+=u&-u) st[u]+=v;
}
int Get1(int u)
{
    int r=0;
    for(;u>0;u-=u&-u) r+=st[u];
    return r;
}
int Get(int l,int r) {return Get1(r) - Get1(l-1);}

void dfs(int u)
{
    in[u]=++Time;
    if (u>n) L[cnt].pb(dep[u]);
    vis[u]=1;
//    cerr<<u<<' '<<dep[u]<<'\n';
    id[u]=cnt;
    for(int v:adj[u]) if (!vis[v])
    {
        dep[v]=dep[u]+w[v];
        dfs(v);
    }
    out[u]=Time;
}

void sol()
{
    cin >> n >> m >> l >> c;
    for1(i,1,n) cin >> a[i];
    for1(i,1,m) cin >> b[i];
    for1(i,1,n)
    {
        int j=upper_bound(a+1,a+1+n,(a[i]-(c%l)+l)%l)-a-1;
        if (j==0) j=n;
        adj[j].pb(i);
        deg[j]++;
        up[i]=j;
        w[i]=c + ((a[i]-(c%l)+l)%l-a[j]+l)%l;
//        cerr<< i<<" <- "<<j<<' '<<w[i]<<'\n';
    }
    for1(i,1,m)
    {
        int j=upper_bound(a+1,a+1+n,b[i])-a-1;
        if (j==0) j=n;
        adj[j].pb(i+n);
        deg[j]++;
        up[i+n]=j;
        w[i+n]=(b[i]-a[j]+l)%l;
//        cerr<< i+n<<" <- "<<j<<' '<<w[i+n]<<'\n';
    }
    for1(i,1,n+m)
    {
        if (!deg[i]) Q.pb(i);
        cycle[i]=1;
    }
    while (!Q.empty())
    {
        int u=Q.back();
        Q.pop_back();
        cycle[u]=0;
        if (!(--deg[up[u]]))  Q.pb(up[u]);
    }
    for1(i,1,n+m)
    {
        if (!vis[i] && cycle[i])
        {
            cnt++;
            dfs(i);
            sum[cnt]=dep[up[i]]+w[i];
//            cerr<<"ca "<<sum[cnt]<<'\n';
            sort(all(L[cnt]));
            for(int x:L[cnt]) nen[cnt].pb(x%sum[cnt]);
            sort(all(nen[cnt]));
            nen[cnt].resize(unique(all(nen[cnt]))-nen[cnt].begin());
            for(int x:L[cnt]) query2[cnt].pb({0,lower_bound(all(nen[cnt]),x%sum[cnt])-nen[cnt].begin()+1,-1,x});
        }
    }
    for1(i,n+1,n+m)
    {
        query1.pb({0,in[i],-1,dep[i]});
    }
    cin >> q;
    for1(i,1,q)
    {
        int u,x;cin >>u>> x;
        int uu=id[u];
        x+=dep[u];
        query1.pb({i,in[u],out[u],x});
        if (cycle[u] && x>=sum[uu])
        {
            x-=sum[uu];
//            cerr<< x<<'\n';
            int j=upper_bound(all(nen[uu]),x%sum[uu])-nen[uu].begin();
            if (j>0) query2[uu].pb({i,1,j,x});
        }
    }
    sort(all(query1));
    for(qr x:query1)
    {
        int id=x.id,u=x.u,v=x.v,w=x.w;
        if (id==0) Update(u,1);
        else res[id]+=Get(u,v);
    }
    for(qr x:query1) if (x.id==0) Update(x.u,-1);
//    cerr<< res[1]<<" po\n";
    for1(i,1,cnt)
    {
        sort(all(query2[i]));
        int pos=0,pre=0;
        for(qr x:query2[i])
        {
            int id=x.id,u=x.u,v=x.v,w=x.w;
//            cerr << id<<' '<<u<<' '<<v<<' '<<w<<'\n';
            if (id==0)
            {
                pos++;
                pre+=w/sum[i];
                Update(u,1);
            }
            else
            {
                res[id]+=(w/sum[i])*pos-pre;
                res[id]+=Get(u,v);
            }
        }
        for(qr x:query2[i]) if (x.id==0) Update(x.u,-1);
    }
    for1(i,1,q) cout << res[i]<<'\n';
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;//cin >> t;
    while (t--) sol();
}
/*
5 3 20 6
0 4 8 12 16
2 11 14
1
1 89
*/

Compilation message (stderr)

harvest.cpp: In function 'void sol()':
harvest.cpp:136:33: warning: unused variable 'w' [-Wunused-variable]
  136 |         int id=x.id,u=x.u,v=x.v,w=x.w;
      |                                 ^

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