Submission #1176422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176422		dzhoz0	Fountain (eJOI20_fountain)	C++20	100 / 100	505 ms	32936 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 1e9
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MOD = 1'000'000'000 + 7;

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
#endif
}
const int MAXN = 1e5;
int n; 
int d[MAXN + 5];
int c[MAXN + 5];

int under[MAXN + 5]; // under[i] = next reservoir

void init_under() {
    stack<int> st;
    for(int i = n; i >= 1; i--) {
        while(!st.empty() && d[st.top()] <= d[i]) st.pop();
        if(!st.empty()) under[i] = st.top();
        else under[i] = n + 1;
        st.push(i);
    }
}

vi g[MAXN + 5];
int h[MAXN + 5];
int dist[MAXN + 5];
int up[MAXN + 5][20];

void dfs(int u, int pre) { 
    up[u][0] = pre;
    for(int j = 1; j < 20; j++) {
        up[u][j] = up[up[u][j - 1]][j - 1];
    }
    for(int v : g[u]) {
        if(v == pre) continue;
        h[v] = h[u] + 1; 
        dist[v] = dist[u] + c[v];
        dfs(v, u);
    }
}

int kth_ancestor(int u, int k) {
    if(h[u] < k) return -1;
    for(int i = 0; (1 << i) <= k; i++) {
        if(k >> i & 1) u = up[u][i];
    }
    return u;
}

int get_dist(int u, int v) {
    // v is child of u
    if(u == n + 1) return dist[v];
    return dist[v] - dist[up[u][0]];
}

int bs(int source, int volume) {
    if(dist[source] <= volume) return 0;
    int l = 0, r = h[source];
    int res = h[source];
    while(l <= r) {
        int mid = (l + r) / 2;
        if(get_dist(kth_ancestor(source, mid), source) >= volume) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    // cout << res << '\n';
    return kth_ancestor(source, res);
}
void solve()
{
    cin >> n;
    int q; cin >> q;
    for(int i = 1; i <= n; i++) cin >> d[i] >> c[i];
    init_under();
    for(int i = 1; i <= n; i++) {
        // cout << i << ' ' << under[i] << '\n';
        // cout << under[i] << '\n';
        g[i].push_back(under[i]);
        g[under[i]].push_back(i);
    }
    memset(up, 0, sizeof(up)); 
    dist[n + 1] = INF;
    h[n + 1] = 1;
    dfs(n + 1, 0);
    // cout << up[4][0] << '\n';
    // cout << get_dist(4, 3) << '\n';
    while(q--) {
        int r, v; cin >> r >> v; 
        cout << bs(r, v) << '\n'; 
    }
}
signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

fountain.cpp: In function 'void setIO(std::string)':
fountain.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40