oj.uz

Submission #940759

# Submission time Handle Problem Language Result Execution time Memory
940759 2024-03-07T15:17:05 Z guagua0407 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 33916 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);
}

struct BIT{
    vector<int> bit;
    int n;
    BIT(int N){
        n=N;
        bit=vector<int>(n,0);
    }
    void update(int pos,int val){
        for(;pos<n;pos+=(pos&-pos)){
            bit[pos]+=val;
        }
    }
    int query(int pos){
        int ans=0;
        for(;pos>0;pos-=(pos&-pos)){
            ans+=bit[pos];
        }
        return ans;
    }
};

const int mxn=200000+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];
int st[mxn*2],en[mxn*2];
vector<pair<int,int>> sta;
vector<pair<int,int>> qs[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
int timer=0;

void dfs(int p,int v){
    st[v]=++timer;
    if(v>=n){
        sta.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);
    }
    en[v]=timer;
}

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]];
        }
        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++){
        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]]);
        }
        for(int i=0;i<(int)curcycle.size();i++){
            int prv=(i-1+(int)curcycle.size())%(int)curcycle.size();
            dis.push_back(dis.back()+d[curcycle[prv]]);
        }
        pre.push_back(dis);
    }
    for(int i=0;i<(int)cycle.size();i++){
        int cnt=0;
        for(auto v:cycle[i]){
            sta.clear();
            dfs(v,v);
            qs[i].insert(qs[i].end(),all(sta));
            sum[i]+=d[v];
            rev[v]=cnt++;
        }
    }
    int q;
    cin>>q;
    vector<pair<ll,pair<int,int>>> qys;
    vector<int> res(q);
    for(int i=0;i<q;i++){
        int v;
        ll t;
        cin>>v>>t;
        v--;
        if(!is_cycle[v]){
            //res[i]=dfs_ans(v,v,t);
            qys.push_back({t+depth[v],{i,v}});
            continue;
        }
        int id=belong[v];
        ll ans=0;
        for(auto p:qs[id]){
            ll cur=t-depth[p.f];
            if(cur<0) continue;
            ans+=cur/sum[id];
            cur%=sum[id];
            int pos=rev[p.s];
            int pos2=upper_bound(all(pre[id]),pre[id][pos]+cur)-pre[id].begin()-1;
            if((pos<=rev[v] and rev[v]<=pos2) or (pos<=rev[v]+(int)cycle[id].size() and rev[v]+(int)cycle[id].size()<=pos2)) ans++;
        }
        res[i]=ans;
    }
    for(int i=n;i<n+m;i++){
        qys.push_back({depth[i],{-1,i}});
    }
    sort(qys.begin(),qys.end());
    BIT T(mxn);
    for(auto query:qys){
        int id=query.s.f;
        int v=query.s.s;
        if(id==-1){
            T.update(st[v],1);
        }
        else{
            res[id]=T.query(en[v])-T.query(st[v]-1);
        }
    }
    for(int i=0;i<q;i++){
        cout<<res[i]<<'\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 9 ms 32860 KB Output is correct
2 Correct 9 ms 33628 KB Output is correct
3 Correct 87 ms 33660 KB Output is correct
4 Correct 8 ms 33588 KB Output is correct
5 Correct 8 ms 33916 KB Output is correct
6 Correct 8 ms 33828 KB Output is correct
7 Correct 9 ms 33836 KB Output is correct
8 Correct 8 ms 33572 KB Output is correct
9 Correct 9 ms 33576 KB Output is correct
10 Correct 8 ms 33576 KB Output is correct
11 Correct 9 ms 33572 KB Output is correct
12 Correct 291 ms 33388 KB Output is correct
13 Correct 400 ms 33424 KB Output is correct
14 Correct 210 ms 33392 KB Output is correct
15 Correct 8 ms 33832 KB Output is correct
16 Correct 9 ms 33832 KB Output is correct
17 Correct 8 ms 33832 KB Output is correct
18 Correct 8 ms 33680 KB Output is correct
19 Correct 8 ms 33712 KB Output is correct
20 Correct 8 ms 33572 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 32860 KB Output is correct
2 Correct 9 ms 33628 KB Output is correct
3 Correct 87 ms 33660 KB Output is correct
4 Correct 8 ms 33588 KB Output is correct
5 Correct 8 ms 33916 KB Output is correct
6 Correct 8 ms 33828 KB Output is correct
7 Correct 9 ms 33836 KB Output is correct
8 Correct 8 ms 33572 KB Output is correct
9 Correct 9 ms 33576 KB Output is correct
10 Correct 8 ms 33576 KB Output is correct
11 Correct 9 ms 33572 KB Output is correct
12 Correct 291 ms 33388 KB Output is correct
13 Correct 400 ms 33424 KB Output is correct
14 Correct 210 ms 33392 KB Output is correct
15 Correct 8 ms 33832 KB Output is correct
16 Correct 9 ms 33832 KB Output is correct
17 Correct 8 ms 33832 KB Output is correct
18 Correct 8 ms 33680 KB Output is correct
19 Correct 8 ms 33712 KB Output is correct
20 Correct 8 ms 33572 KB Output is correct
21 Execution timed out 5027 ms 33116 KB Time limit exceeded
22 Halted 0 ms 0 KB -