oj.uz

Submission #1094303

# Submission time Handle Problem Language Result Execution time Memory
1094303 2024-09-29T10:21:45 Z vjudge1 Harvest (JOI20_harvest) C++17
5 / 100
 132 ms 60432 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38488 KB Output is correct
2 Correct 22 ms 39424 KB Output is correct
3 Correct 21 ms 39268 KB Output is correct
4 Correct 22 ms 39204 KB Output is correct
5 Correct 24 ms 39384 KB Output is correct
6 Correct 22 ms 39380 KB Output is correct
7 Correct 21 ms 39384 KB Output is correct
8 Correct 22 ms 39260 KB Output is correct
9 Correct 26 ms 39324 KB Output is correct
10 Correct 26 ms 39260 KB Output is correct
11 Correct 22 ms 39256 KB Output is correct
12 Correct 22 ms 39384 KB Output is correct
13 Correct 23 ms 39592 KB Output is correct
14 Correct 21 ms 39624 KB Output is correct
15 Correct 21 ms 39384 KB Output is correct
16 Correct 20 ms 39384 KB Output is correct
17 Correct 25 ms 39384 KB Output is correct
18 Correct 22 ms 39384 KB Output is correct
19 Correct 20 ms 39328 KB Output is correct
20 Correct 21 ms 39376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 60432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38488 KB Output is correct
2 Correct 22 ms 39424 KB Output is correct
3 Correct 21 ms 39268 KB Output is correct
4 Correct 22 ms 39204 KB Output is correct
5 Correct 24 ms 39384 KB Output is correct
6 Correct 22 ms 39380 KB Output is correct
7 Correct 21 ms 39384 KB Output is correct
8 Correct 22 ms 39260 KB Output is correct
9 Correct 26 ms 39324 KB Output is correct
10 Correct 26 ms 39260 KB Output is correct
11 Correct 22 ms 39256 KB Output is correct
12 Correct 22 ms 39384 KB Output is correct
13 Correct 23 ms 39592 KB Output is correct
14 Correct 21 ms 39624 KB Output is correct
15 Correct 21 ms 39384 KB Output is correct
16 Correct 20 ms 39384 KB Output is correct
17 Correct 25 ms 39384 KB Output is correct
18 Correct 22 ms 39384 KB Output is correct
19 Correct 20 ms 39328 KB Output is correct
20 Correct 21 ms 39376 KB Output is correct
21 Incorrect 132 ms 60432 KB Output isn't correct
22 Halted 0 ms 0 KB -