oj.uz

답안 #1006242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006242 2024-06-23T15:14:39 Z Unforgettablepl 수확 (JOI20_harvest) C++17
5 / 100
 5000 ms 103500 KB 
#include <bits/stdc++.h>
using namespace std;


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<long long,long long>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;

#define int long long

const int INF = 1e18;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,l,c;
    cin >> n >> m >> l >> c;
    vector<int> employee(n+1);
    vector<int> apple(m);
    vector<pair<int,int>> adj(n+1);
    vector<vector<int>> revadj(n+1);
    for(int i=1;i<=n;i++)cin>>employee[i];
    for(int&i:apple)cin>>i;
    for(int i=1;i<=n;i++){
        int modded = c%l;
        int iter = 0;
        for(int jump=131072;jump;jump/=2){
            if(iter+jump>n)continue;
            if((l+employee[i]-employee[(n-iter-jump+i)%n +1])%l < modded)iter+=jump;
        }
        iter++;
        if(iter==n+1){
            adj[i] = {i,(c/l)*l + l};
            continue;
        }
        adj[i] = {(n-iter+i)%n +1,(c/l)*l + (l+employee[i]-employee[(n-iter+i)%n +1])%l};
        revadj[adj[i].first].emplace_back(i);
    }
    vector<int> depth(n+1);
    vector<bool> visited(n+1);
    vector<int> heads;
    function<void (int)> front_dfs = [&](int x){
        if(visited[x])return;
        visited[x]=true;
        front_dfs(adj[x].first);
        if(depth[adj[x].first]==0)heads.emplace_back(x);
        depth[x] = depth[adj[x].first]+adj[x].second;
    };
    for(int i=1;i<=n;i++)if(!visited[i])front_dfs(i);
    vector<vector<int>> apples(n+1);
    vector<vector<pair<int,int>>> queries(n+1);
    for(int&i:apple){
        int start = -1;
        if(i<employee[1])start = n;
        else {
            start = upper_bound(employee.begin()+1,employee.end(),i)-employee.begin()-1;
        }
        apples[start].emplace_back((l+i-employee[start])%l);
    }
    int q;
    cin >> q;
    vector<int> ans(q+1);
    for(int i=1;i<=q;i++){
        int v,t;
        cin >> v >> t;
        queries[v].emplace_back(t,i);
    }
    visited = vector<bool>(n+1);
    int uid = 0;
    function<orderedset(int)> calc_linear_dfs = [&](int x){
        orderedset curr;
        if(visited[x])return curr;
        visited[x] = true;
        for(int&i:revadj[x]){
            auto t = calc_linear_dfs(i);
            if(curr.size()<t.size())swap(curr,t);
            for(auto j:t)curr.insert(j);
        }
        for(int&i:apples[x])curr.insert({i+depth[x],++uid});
        for(auto[t,idx]:queries[x]){
            ans[idx] = curr.order_of_key({t+depth[x],INF});
        }
        return curr;
    };
    for(int&i:heads){
        auto t = calc_linear_dfs(i);
        orderedset curr;
        int cycle_len = depth[adj[i].first];
        int offset = 0;
        for(auto [x,y]:t)curr.insert({(x-adj[i].second)%cycle_len,y});
        for(auto [x,y]:t)offset-=(x-adj[i].second)/cycle_len;
        function<void(int,int)> calc = [&](int x,int len){
            for(auto[t,idx]:queries[x]){
                t-=len;
                if(t<0)continue;
                ans[idx]+=curr.size()*(t/cycle_len);
                t%=cycle_len;
                ans[idx]+=curr.order_of_key({t,INF});
                ans[idx]+=offset;
            }
            if(x==i)return;
            calc(adj[x].first,len+adj[x].second);
        };
        calc(adj[i].first,adj[i].second);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 1380 KB Output is correct
4 Correct 11 ms 1372 KB Output is correct
5 Correct 98 ms 2060 KB Output is correct
6 Correct 93 ms 2140 KB Output is correct
7 Correct 101 ms 2128 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 3 ms 1288 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 111 ms 2052 KB Output is correct
13 Correct 102 ms 2132 KB Output is correct
14 Correct 53 ms 1372 KB Output is correct
15 Correct 48 ms 1660 KB Output is correct
16 Correct 51 ms 1620 KB Output is correct
17 Correct 47 ms 1552 KB Output is correct
18 Correct 54 ms 1628 KB Output is correct
19 Correct 56 ms 1628 KB Output is correct
20 Correct 56 ms 1652 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 8892 KB Output is correct
2 Correct 353 ms 34644 KB Output is correct
3 Correct 147 ms 42884 KB Output is correct
4 Correct 151 ms 43360 KB Output is correct
5 Execution timed out 5028 ms 103500 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 1380 KB Output is correct
4 Correct 11 ms 1372 KB Output is correct
5 Correct 98 ms 2060 KB Output is correct
6 Correct 93 ms 2140 KB Output is correct
7 Correct 101 ms 2128 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 3 ms 1288 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 111 ms 2052 KB Output is correct
13 Correct 102 ms 2132 KB Output is correct
14 Correct 53 ms 1372 KB Output is correct
15 Correct 48 ms 1660 KB Output is correct
16 Correct 51 ms 1620 KB Output is correct
17 Correct 47 ms 1552 KB Output is correct
18 Correct 54 ms 1628 KB Output is correct
19 Correct 56 ms 1628 KB Output is correct
20 Correct 56 ms 1652 KB Output is correct
21 Correct 69 ms 8892 KB Output is correct
22 Correct 353 ms 34644 KB Output is correct
23 Correct 147 ms 42884 KB Output is correct
24 Correct 151 ms 43360 KB Output is correct
25 Execution timed out 5028 ms 103500 KB Time limit exceeded
26 Halted 0 ms 0 KB -