oj.uz

Submission #1094305

# Submission time Handle Problem Language Result Execution time Memory
1094305 2024-09-29T10:23:25 Z vjudge1 Harvest (JOI20_harvest) C++17
5 / 100
 166 ms 115012 KB 
#include<bits/stdc++.h>
using namespace std;
#define int ll
#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--)

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

const ll maxn = 1e6 + 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 44 ms 94800 KB Output is correct
2 Correct 51 ms 95680 KB Output is correct
3 Correct 46 ms 95820 KB Output is correct
4 Correct 46 ms 95600 KB Output is correct
5 Correct 46 ms 95832 KB Output is correct
6 Correct 47 ms 95788 KB Output is correct
7 Correct 50 ms 95820 KB Output is correct
8 Correct 46 ms 95560 KB Output is correct
9 Correct 46 ms 95568 KB Output is correct
10 Correct 50 ms 95568 KB Output is correct
11 Correct 46 ms 95576 KB Output is correct
12 Correct 46 ms 95828 KB Output is correct
13 Correct 58 ms 96008 KB Output is correct
14 Correct 47 ms 95960 KB Output is correct
15 Correct 55 ms 95688 KB Output is correct
16 Correct 68 ms 95708 KB Output is correct
17 Correct 52 ms 95692 KB Output is correct
18 Correct 51 ms 95692 KB Output is correct
19 Correct 43 ms 95680 KB Output is correct
20 Correct 46 ms 95692 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94800 KB Output is correct
2 Correct 51 ms 95680 KB Output is correct
3 Correct 46 ms 95820 KB Output is correct
4 Correct 46 ms 95600 KB Output is correct
5 Correct 46 ms 95832 KB Output is correct
6 Correct 47 ms 95788 KB Output is correct
7 Correct 50 ms 95820 KB Output is correct
8 Correct 46 ms 95560 KB Output is correct
9 Correct 46 ms 95568 KB Output is correct
10 Correct 50 ms 95568 KB Output is correct
11 Correct 46 ms 95576 KB Output is correct
12 Correct 46 ms 95828 KB Output is correct
13 Correct 58 ms 96008 KB Output is correct
14 Correct 47 ms 95960 KB Output is correct
15 Correct 55 ms 95688 KB Output is correct
16 Correct 68 ms 95708 KB Output is correct
17 Correct 52 ms 95692 KB Output is correct
18 Correct 51 ms 95692 KB Output is correct
19 Correct 43 ms 95680 KB Output is correct
20 Correct 46 ms 95692 KB Output is correct
21 Incorrect 166 ms 115012 KB Output isn't correct
22 Halted 0 ms 0 KB -