oj.uz

Submission #689915

# Submission time Handle Problem Language Result Execution time Memory
689915 2023-01-29T18:12:48 Z vjudge1 Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 12664 KB 
#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, ll>
#define oo 1e9

using namespace std;

int n;
vector<ll> capacity, diameter;

vector<vector<int>> st;
vector<int> LOGS;

vector<int> after;

void build(){
    LOGS.resize(n + 1);
    LOGS[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        LOGS[i] = LOGS[i / 2] + 1;
    }
    

    int MaxLog = 0;
    int a = n;
    while(a > 0){
        a >>= 1;
        MaxLog++;
    }
    
    st.resize(MaxLog, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        st[0][i] = diameter[i];
    }
    
    for (int j = 1; j < MaxLog; j++)
    {
        for (int i = 0; i <= n - (1 << j); i++)
        {
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int ask(int l, int r){
    int d = r - l + 1;
    int j = LOGS[d];
    return max(st[j][l], st[j][r - (1 << j) + 1]);
}

int main(){
    int q;
    cin >> n >> q;
    n += 1;
    capacity.resize(n + 1);
    diameter.resize(n + 1);
    after.resize(n + 1);
    for (int i = 1; i < n; i++)
    {
        scanf("%d %lld", &diameter[i], &capacity[i]);
    }
    diameter[n] = oo * 2;
    capacity[n] = 1e18;

    build();

    vector<int> inputCount(n + 1);
    for (int i = 1; i < n; i++)
    {
        int l = i, r = n;
        while(l < r){
            int mid = (l + r) / 2;
            if(ask(l, mid) > diameter[i]){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        after[i] = r;
        inputCount[r]++;
    }
    after[n] = 0;

    int mp[n + 1][2];
    vector<vector<pii>> chains;
    vector<bool> visited(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        if(visited[i]) continue;
        visited[i] = true;

        chains.push_back({{0, 0}, {i, capacity[i]}});
        auto &lastChain = chains[chains.size() - 1];
        
        mp[i][0] = chains.size() - 1;
        mp[i][1] = lastChain.size() - 1;

        int j = after[i];
        while(j != 0 && !visited[j]){
            visited[j] = true;
            lastChain.push_back({j, lastChain[lastChain.size() - 1].second + capacity[j]});
            mp[j][0] = chains.size() - 1;
            mp[j][1] = lastChain.size() - 1;
            j = after[j];
        }
    }
    
    
    while(q--){
        ll j, v; scanf("%lld %lld", &j, &v);
        pii ans = {0, 0};
        while(v > 0){
            vector<pii> &chain = chains[mp[j][0]];
            ans = chain[chain.size() - 1];
            int l = mp[j][1], r = chain.size() - 1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(chain[mid].second - chain[mp[j][1] - 1].second >= v){
                    ans = chain[mid];
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            v -= ans.second - chain[mp[j][1] - 1].second;
            //cout << v << ' ' << ans.first << '\n'; 

            if(v > 0) j = after[ans.first];
        }
        if(ans.first == n) ans.first = 0;
        cout << ans.first << '\n';
    }
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:64:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*' {aka 'long long int*'} [-Wformat=]
   64 |         scanf("%d %lld", &diameter[i], &capacity[i]);
      |                ~^
      |                 |
      |                 int*
      |                %lld
fountain.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d %lld", &diameter[i], &capacity[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:115:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         ll j, v; scanf("%lld %lld", &j, &v);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 12664 KB Output is correct
2 Correct 101 ms 11948 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 88 ms 12664 KB Output is correct
9 Correct 101 ms 11948 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Execution timed out 1595 ms 8764 KB Time limit exceeded
12 Halted 0 ms 0 KB -