oj.uz

Submission #1106727

# Submission time Handle Problem Language Result Execution time Memory
1106727 2024-10-31T01:49:18 Z Bananabread Harvest (JOI20_harvest) C++17
0 / 100
 181 ms 79788 KB 
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll a[200001],b[200001];
ll n,m,l,c,q;
vector<pair<ll,ll>> adj[500001],adjrev[500001];
ll vis[500001];
ll dist[500001];
ll cnt;
vector<vector<pair<ll,ll>>> compart;
vector<vector<ll>> pref;
vector<ll> len;
ll num[500001];
ll insub[500001];
bool inloop[500001];
ll root;
void dfs(ll u){
    if(root) return ;
    if(vis[u]){
        root=u;
        return ;
    }
    vis[u]=1;
    for(auto [v,w]:adj[u]){
        dfs(v);
    }
}
void dfs1(ll u=root,ll d=0,ll par=0){
    vis[u]=1;
    num[u]=cnt;
    if(u>n){
        insub[u]=1;
        compart[cnt].push_back({d%len[cnt],d/len[cnt]});
    }
    for(auto [v,w]:adjrev[u]){
        if(v==root) continue;
        //cout<<u<<' '<<v<<' '<<root<<ntr;
        dfs1(v,d+w,u);
        insub[u]+=insub[v];
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n>>m>>l>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        ll t=((a[i]-c)%l+l)%l;
        ll pos=upper_bound(a+1,a+n+1,t)-a-1;
        if(pos==0) pos=n;
        //if(i==j) continue;
        ll v=((a[i]-a[pos])%l+l)%l;
        ll cost=(c-v+l-1)/l*l+v;
//        cout<<i<<' '<<pos<<' '<<cost<<ntr;
        adj[i].push_back({pos,cost});
        adjrev[pos].push_back({i,cost});
    }
    for(int i=1;i<=m;i++){
        ll v=upper_bound(a+1,a+n+1,b[i])-a-1;
        if(v==0) v=n;
        ll cost=((b[i]-a[v])%l+l)%l;
        adj[i+n].push_back({v,cost});
        adjrev[v].push_back({i+n,cost});
//        cout<<i+n<<' '<<v<<' '<<cost<<ntr;
    }
    compart.push_back({});
    pref.push_back({});
    len.push_back(0);
    for(int i=1;i<=m;i++){
        if(vis[i+n]) continue;
        root=0,dfs(i+n);
        cnt++;
        compart.push_back({});
        pref.push_back({});
        ll p=root;
        dist[root]=0;
        while(true){
            inloop[p]=1;
            auto [v,w]=adj[p][0];
            if(v==root){
                len.push_back(dist[p]+w);
                break;
            }
            dist[v]=dist[p]+w;
            p=v;
        }
        dfs1();
        sort(compart[cnt].begin(),compart[cnt].end());
        pref[cnt].push_back(compart[cnt][0].second);
        for(int i=1;i<compart[cnt].size();i++){
            pref[cnt].push_back(pref[cnt].back()+compart[cnt][i].second);
        }
    }
//    for(int i=1;i<=n+m;i++){
//        cout<<insub[i]<<' ';
//    }
//    cout<<ntr;
    cin>>q;
    for(int i=1;i<=q;i++){
        ll u,t;
        cin>>u>>t;
        t-=dist[u];
        if(!inloop[u]){
            cout<<insub[u]<<ntr;
            continue;
        }
        else{
            ll ans=insub[u]*(dist[u]>0);
            ll p=t/len[num[u]];
            ll q=t%len[num[u]];
            ll lo=0,hi=compart[num[u]].size()-1,pos=-1;
            while(lo<=hi){
                ll mid=(lo+hi)/2;
                if(compart[cnt][mid].first<=q) pos=mid,lo=mid+1;
                else hi=mid-1;
            }
            ans+=(compart[num[u]].size())*p-pref[num[u]].back();
            ans+=pos+1;
            cout<<ans<<ntr;
        }

    }
}

Compilation message

harvest.cpp: In function 'int main()':
harvest.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i=1;i<compart[cnt].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33360 KB Output is correct
2 Correct 8 ms 34040 KB Output is correct
3 Correct 8 ms 33872 KB Output is correct
4 Incorrect 7 ms 31824 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 41032 KB Output is correct
2 Correct 123 ms 57684 KB Output is correct
3 Correct 90 ms 58912 KB Output is correct
4 Correct 109 ms 59388 KB Output is correct
5 Correct 114 ms 77896 KB Output is correct
6 Correct 110 ms 77904 KB Output is correct
7 Correct 78 ms 56380 KB Output is correct
8 Correct 79 ms 53936 KB Output is correct
9 Correct 130 ms 79688 KB Output is correct
10 Correct 117 ms 79788 KB Output is correct
11 Correct 165 ms 78788 KB Output is correct
12 Correct 181 ms 78664 KB Output is correct
13 Correct 180 ms 78668 KB Output is correct
14 Correct 146 ms 78540 KB Output is correct
15 Incorrect 123 ms 70216 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33360 KB Output is correct
2 Correct 8 ms 34040 KB Output is correct
3 Correct 8 ms 33872 KB Output is correct
4 Incorrect 7 ms 31824 KB Output isn't correct
5 Halted 0 ms 0 KB -