oj.uz

Submission #563550

# Submission time Handle Problem Language Result Execution time Memory
563550 2022-05-17T12:57:17 Z beep_boop Fountain (eJOI20_fountain) C++17
100 / 100
 1163 ms 39944 KB 
/*
 * Created at 5:56 PM on 17 May, 2022
 */

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <functional>
#include <stack>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define trav(a, x) for(auto& (a): (x))
#define DO if(true)

#define mp make_pair
#define pb push_back
#define eb emplace_back

//#define int int64_t

typedef vector<int> vi;
typedef pair<int, int> pi;

#define mod 1000000007

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

template<typename T>
void read(vector<T> &a, int n) {
    a.resize(n);
    for (auto &x: a) cin >> x;
}

template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
    out << "(";
    out << v.first << ", " << v.second;
    return out << ")";
}

template<class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
    out << "[";
    list(i, SZ(v)) {
        if (i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

template<typename T>
void print(vector<T> &a) {
    for (const auto &x: a) cout << x << ' ';
    cout << '\n';
}

template<typename T>
void MOD(T &x, int m = mod) {
    x %= m;
    if (x < 0) x += m;
}

#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void dbg(const char *name, T &&arg1) {
    cout << name << " : " << arg1 << '\n';
}

template<typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&... args) {
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    dbg(comma + 1, args...);
}

template<class T>
void read(T &x) {
    cin >> x;
}

template<class T, class... U>
void read(T &t, U &... u) {
    read(t);
    read(u...);
}

int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }

int ceil_div(int a, int b) { return (a + b - 1) / b; }

using ll = int64_t;

const int N = int(1e5) + 10;
const int B = 17;
int n, q;
vi d, c;
vi nex;
vt<vt<ll>> sum, node;

bool ok(int r, int up, int v){
    ll cur_sum = c[r];
    int cur_node = r;

    list(i, B){
        if((up >> i) & 1){
            cur_sum += sum[cur_node][i];
            cur_node = node[cur_node][i];

            if(cur_node == -1){
//                trace(r, up, v, cur_node, cur_sum);
                return true;
            }
        }
    }

//    trace(r, up, v, cur_node, cur_sum);

    return cur_sum >= v;
}

int find_node(int x, int lev){
    int ans = x;
    list(i, B){
        if((lev >> i) & 1){
            ans = node[ans][i];

            if(ans == -1){
                break;
            }
        }
    }

    return ans;
}

int32_t main() {
    setIO();

    read(n, q);
    d.resize(n);
    c.resize(n);
    list(i, n){
        read(d[i], c[i]);
    }

    nex.resize(n, -1);
    stack<int> s;

    for(int i = n - 1; i >= 0; i--){
        while(!s.empty() and d[s.top()] <= d[i]){
            s.pop();
        }

        if(!s.empty()) {
            nex[i] = s.top();
        }else {
            nex[i] = -1;
        }
        s.push(i);
    }

    sum.resize(n, vt<ll>(B, ll(2e9)));
    node.resize(n, vt<ll>(B, -1));
    list(i, n){
        sum[i][0] = nex[i] != -1 ? c[nex[i]] : ll(2e9);
        node[i][0] = nex[i];
    }

//    trace(nex);

    for(int lev = 1; lev < B; lev++){
        list(i, n) {
            sum[i][lev] = sum[i][lev - 1] + (node[i][lev - 1] != -1 ? sum[node[i][lev - 1]][lev - 1] : ll(2e9));
            node[i][lev] = node[i][lev - 1] == -1 ? -1 : node[node[i][lev - 1]][lev - 1];

//            trace(i, lev, sum[i][lev]);
//            trace(i, lev, node[i][lev]);
        }
    }

    int r, v;
    while(q--){
        read(r, v);
        r--;

        int lo = 0, hi = n;
        int res = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;

            if(ok(r, mid, v)){
                hi = mid - 1;
                res = mid;
            }else {
                lo = mid + 1;
            }
        }

        int ans = find_node(r, res);
        cout << ans + 1 << '\n';

        assert(res != -1);
    }

    return 0;
}

Compilation message

fountain.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
fountain.cpp:24:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
fountain.cpp:64:5: note: in expansion of macro 'list'
   64 |     list(i, SZ(v)) {
      |     ^~~~
fountain.cpp: In function 'bool ok(int, int, int)':
fountain.cpp:24:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
fountain.cpp:125:5: note: in expansion of macro 'list'
  125 |     list(i, B){
      |     ^~~~
fountain.cpp: In function 'int find_node(int, int)':
fountain.cpp:24:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
fountain.cpp:144:5: note: in expansion of macro 'list'
  144 |     list(i, B){
      |     ^~~~
fountain.cpp: In function 'int32_t main()':
fountain.cpp:24:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
fountain.cpp:163:5: note: in expansion of macro 'list'
  163 |     list(i, n){
      |     ^~~~
fountain.cpp:24:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
fountain.cpp:185:5: note: in expansion of macro 'list'
  185 |     list(i, n){
      |     ^~~~
fountain.cpp:24:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
fountain.cpp:193:9: note: in expansion of macro 'list'
  193 |         list(i, n) {
      |         ^~~~

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 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 612 KB Output is correct
7 Correct 2 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 36716 KB Output is correct
2 Correct 850 ms 34372 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 612 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 787 ms 36716 KB Output is correct
9 Correct 850 ms 34372 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 289 ms 21368 KB Output is correct
12 Correct 1163 ms 39944 KB Output is correct
13 Correct 836 ms 39084 KB Output is correct
14 Correct 335 ms 38500 KB Output is correct
15 Correct 213 ms 38732 KB Output is correct