oj.uz

Submission #939034

# Submission time Handle Problem Language Result Execution time Memory
939034 2024-03-06T03:53:38 Z guagua0407 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 3712 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=6000+5;
int a[mxn];
int b[mxn];
int nxt[mxn*2];
bool visited[mxn*2];
bool is_cycle[mxn*2];
vector<pair<int,ll>> adj[mxn*2];
int belong[mxn*2];
ll depth[mxn*2];
ll d[mxn*2];
ll sum[mxn*2];
int rev[mxn*2];
vector<pair<int,int>> st;
vector<pair<int,int>> qs[mxn];
vector<vector<ll>> pre;
int n,m,l,c;

void dfs(int p,int v){
    if(v>=n){
        st.push_back({v,p});
    }
    for(auto u:adj[v]){
        if(is_cycle[u.f]) continue;
        depth[u.f]=depth[v]+u.s;
        dfs(p,u.f);
    }
}

int dfs_ans(int p,int v,ll t){
    if(v>=n){
        if(depth[v]-depth[p]<=t) return 1;
        else return 0;
    }
    int ans=0;
    for(auto u:adj[v]){
        ans+=dfs_ans(p,u.f,t);
    }
    return ans;
}

signed main() {_
    cin>>n>>m>>l>>c;
    ll C=c;
    c%=l;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        if(a[i]-c>=a[0]){
            nxt[i]=upper_bound(a,a+n,a[i]-c)-a-1;
            d[i]=a[i]-a[nxt[i]];
        }
        else{
            int val=(a[i]-c+l);
            nxt[i]=upper_bound(a,a+n,val)-a-1;
            d[i]=a[i]+l-a[nxt[i]];
            //cout<<"sir "<<i<<' '<<nxt[i]<<'\n';
        }
        if(d[i]==0){
            d[i]=(C+l-1)/l*l;
        }
        else{
            d[i]+=1ll*(C/l)*l;
        }
    }
    for(int i=0;i<m;i++){
        if(b[i]>=a[0]){
            nxt[i+n]=upper_bound(a,a+n,b[i])-a-1;
            d[i+n]=b[i]-a[nxt[i+n]];
        }
        else{
            int val=(b[i]+l);
            nxt[i+n]=upper_bound(a,a+n,val)-a-1;
            d[i+n]=b[i]+l-a[nxt[i+n]];
        }
    }
    for(int i=0;i<n+m;i++){
        //cout<<nxt[i]<<' '<<d[i]<<'\n';
        adj[nxt[i]].push_back({i,d[i]});
    }
    vector<vector<int>> cycle;
    for(int i=0;i<n+m;i++){
        if(visited[i]) continue;
        int x=i;
        vector<int> tmp;
        while(!visited[x]){
            visited[x]=true;
            tmp.push_back(x);
            x=nxt[x];
        }
        bool ok=false;
        for(auto v:tmp){
            ok|=(v==x);
            is_cycle[v]=ok;
        }
        if(!ok) continue;
        vector<int> curcycle;
        for(auto v:tmp){
            if(is_cycle[v]){
                curcycle.push_back(v);
                belong[v]=(int)cycle.size();
            }
        }
        cycle.push_back(curcycle);
        vector<ll> dis;
        dis.push_back(0);
        for(int i=1;i<(int)curcycle.size();i++){
            dis.push_back(dis.back()+d[curcycle[i-1]]);
        }
        pre.push_back(dis);
    }
    //return 0;
    for(int i=0;i<(int)cycle.size();i++){
        int cnt=0;
        for(auto v:cycle[i]){
            st.clear();
            dfs(v,v);
            qs[i].insert(qs[i].end(),all(st));
            sum[i]+=d[v];
            rev[v]=cnt++;
            //cout<<v<<' ';
        }
        //cout<<'\n';
    }
    //return 0;
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int v;
        ll t;
        cin>>v>>t;
        v--;
        if(!is_cycle[v]){
            //return 0;
            cout<<dfs_ans(v,v,t)<<'\n';
            continue;
        }
        //continue;
        int id=belong[v];
        ll ans=0;
        for(auto p:qs[id]){
            ll cur=t-depth[p.f];
            if(cur<0) continue;
            //assert(sum[id]!=0);
            ans+=cur/sum[id];
            cur%=sum[id];
            //continue;
            int pos=rev[p.s];
            //cout<<p.f<<' '<<p.s<<'\n';
            //cout<<"pos "<<id<<' '<<pos<<' '<<pre[id].size()<<'\n';
            //continue;
            if(pre[id][pos]+cur>=sum[id]){
                if(pos<=rev[v]){
                    ans++;
                    continue;
                }
                cur-=(sum[id]-pre[id][pos]);
                pos=0;
            }
            int pos2=upper_bound(all(pre[id]),pre[id][pos]+cur)-pre[id].begin()-1;
            //cout<<"pos "<<pos<<' '<<pos2<<'\n';
            if(pos<=rev[v] and rev[v]<=pos2) ans++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
/*
1 1 2 5
0
1
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
*/

Compilation message

harvest.cpp: In function 'void setIO(std::string)':
harvest.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 4 ms 1672 KB Output is correct
3 Correct 80 ms 1884 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 48 ms 1816 KB Output is correct
6 Correct 42 ms 1832 KB Output is correct
7 Correct 43 ms 1624 KB Output is correct
8 Correct 3 ms 1368 KB Output is correct
9 Correct 2 ms 1368 KB Output is correct
10 Correct 2 ms 1368 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 295 ms 1584 KB Output is correct
13 Correct 349 ms 1880 KB Output is correct
14 Correct 202 ms 1656 KB Output is correct
15 Correct 25 ms 1676 KB Output is correct
16 Correct 29 ms 1880 KB Output is correct
17 Correct 25 ms 1628 KB Output is correct
18 Correct 22 ms 1624 KB Output is correct
19 Correct 22 ms 1656 KB Output is correct
20 Correct 22 ms 1624 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 3712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 4 ms 1672 KB Output is correct
3 Correct 80 ms 1884 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 48 ms 1816 KB Output is correct
6 Correct 42 ms 1832 KB Output is correct
7 Correct 43 ms 1624 KB Output is correct
8 Correct 3 ms 1368 KB Output is correct
9 Correct 2 ms 1368 KB Output is correct
10 Correct 2 ms 1368 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 295 ms 1584 KB Output is correct
13 Correct 349 ms 1880 KB Output is correct
14 Correct 202 ms 1656 KB Output is correct
15 Correct 25 ms 1676 KB Output is correct
16 Correct 29 ms 1880 KB Output is correct
17 Correct 25 ms 1628 KB Output is correct
18 Correct 22 ms 1624 KB Output is correct
19 Correct 22 ms 1656 KB Output is correct
20 Correct 22 ms 1624 KB Output is correct
21 Execution timed out 5033 ms 3712 KB Time limit exceeded
22 Halted 0 ms 0 KB -