oj.uz

답안 #939119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939119 2024-03-06T05:54:14 Z guagua0407 수확 (JOI20_harvest) C++17
5 / 100
 5000 ms 32244 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=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];
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]]);
        }
        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);
    }
    //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;
            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) or (pos<=rev[v]+(int)cycle[id].size() and rev[v]+(int)cycle[id].size()<=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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 7 ms 27816 KB Output is correct
3 Correct 86 ms 28120 KB Output is correct
4 Correct 9 ms 27740 KB Output is correct
5 Correct 46 ms 27912 KB Output is correct
6 Correct 47 ms 27996 KB Output is correct
7 Correct 49 ms 27996 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Correct 7 ms 27560 KB Output is correct
10 Correct 6 ms 27740 KB Output is correct
11 Correct 6 ms 27484 KB Output is correct
12 Correct 299 ms 27832 KB Output is correct
13 Correct 419 ms 27920 KB Output is correct
14 Correct 209 ms 27740 KB Output is correct
15 Correct 29 ms 27940 KB Output is correct
16 Correct 30 ms 27740 KB Output is correct
17 Correct 29 ms 27736 KB Output is correct
18 Correct 25 ms 27740 KB Output is correct
19 Correct 27 ms 27740 KB Output is correct
20 Correct 26 ms 27912 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5041 ms 32244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 7 ms 27816 KB Output is correct
3 Correct 86 ms 28120 KB Output is correct
4 Correct 9 ms 27740 KB Output is correct
5 Correct 46 ms 27912 KB Output is correct
6 Correct 47 ms 27996 KB Output is correct
7 Correct 49 ms 27996 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Correct 7 ms 27560 KB Output is correct
10 Correct 6 ms 27740 KB Output is correct
11 Correct 6 ms 27484 KB Output is correct
12 Correct 299 ms 27832 KB Output is correct
13 Correct 419 ms 27920 KB Output is correct
14 Correct 209 ms 27740 KB Output is correct
15 Correct 29 ms 27940 KB Output is correct
16 Correct 30 ms 27740 KB Output is correct
17 Correct 29 ms 27736 KB Output is correct
18 Correct 25 ms 27740 KB Output is correct
19 Correct 27 ms 27740 KB Output is correct
20 Correct 26 ms 27912 KB Output is correct
21 Execution timed out 5041 ms 32244 KB Time limit exceeded
22 Halted 0 ms 0 KB -