oj.uz

답안 #1112115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112115 2024-11-13T16:39:41 Z lam 수확 (JOI20_harvest) C++14
20 / 100
 240 ms 79688 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[num[u]][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 'void dfs(long long int)':
harvest.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto [v,w]:adj[u]){
      |              ^
harvest.cpp: In function 'void dfs1(long long int, long long int, long long int)':
harvest.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto [v,w]:adjrev[u]){
      |              ^
harvest.cpp: In function 'int main()':
harvest.cpp:84:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |             auto [v,w]=adj[p][0];
      |                  ^
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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 8 ms 33872 KB Output is correct
3 Correct 8 ms 33616 KB Output is correct
4 Incorrect 9 ms 31824 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 36936 KB Output is correct
2 Correct 118 ms 57416 KB Output is correct
3 Correct 107 ms 59208 KB Output is correct
4 Correct 117 ms 59264 KB Output is correct
5 Correct 143 ms 77896 KB Output is correct
6 Correct 127 ms 77860 KB Output is correct
7 Correct 109 ms 56240 KB Output is correct
8 Correct 97 ms 53936 KB Output is correct
9 Correct 159 ms 79688 KB Output is correct
10 Correct 130 ms 79688 KB Output is correct
11 Correct 223 ms 78664 KB Output is correct
12 Correct 240 ms 78816 KB Output is correct
13 Correct 234 ms 78664 KB Output is correct
14 Correct 161 ms 78676 KB Output is correct
15 Correct 144 ms 70216 KB Output is correct
16 Correct 112 ms 67912 KB Output is correct
17 Correct 120 ms 67768 KB Output is correct
18 Correct 66 ms 45460 KB Output is correct
19 Correct 60 ms 45504 KB Output is correct
20 Correct 110 ms 57428 KB Output is correct

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 8 ms 33872 KB Output is correct
3 Correct 8 ms 33616 KB Output is correct
4 Incorrect 9 ms 31824 KB Output isn't correct
5 Halted 0 ms 0 KB -