Submission #563550

#	Time	Username	Problem	Language	Result	Execution time	Memory
563550		beep_boop	Fountain (eJOI20_fountain)	C++17	100 / 100	1163 ms	39944 KiB

fountain

/*
 * 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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40