oj.uz

Submission #1023413

# Submission time Handle Problem Language Result Execution time Memory
1023413 2024-07-14T18:04:40 Z armashka Fountain (eJOI20_fountain) C++17
100 / 100
 218 ms 41132 KB 
#include<bits/stdc++.h>

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

using namespace std;

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ft first
#define sd second
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
const int N = 3e5 + 10;
const int M = 1e6 + 5;
const int B = 316;
const ll msize = 2;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const long double Phi = acos(-1);
const long long inf = 2e18;
const vector <pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

ll binmul(ll x, ll ti, ll m);
ll binpow(ll x, ll ti, ll m);

ll n, q, d[N], c[N];
vector <int> g[N];
ll pref[N], up[N][19];

void dfs(int v, int pr) {
    up[v][0] = pr;
    pref[v] += c[v];

    for (int i = 1; i <= 18; ++ i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (auto to : g[v]) {
        if (to != pr) {
            pref[to] = pref[v];
            dfs(to, v);
        }
    }
}

int get(int u, ll x) {
    if (c[u] >= x) return u;
    int cur = u;
    for (int i = 18; i >= 0; -- i) {
        int v = up[u][i];
        if (pref[cur] - pref[v] + c[v] < x) u = v; 
    }
    int ans = up[u][0];
    return (ans == n + 1 ? 0 : ans);
}

const void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        cin >> d[i] >> c[i];
    }

    c[n + 1] = d[n + 1] = 1e9+1;
    stack<int> st;
    st.push(n + 1);

    for (int i = n; i >= 1; -- i) {
        while (st.size() && d[st.top()] <= d[i]) st.pop();

        int j = st.top();
        g[j].pb(i);
        
        st.push(i);
    }

    dfs(n + 1, n + 1);

    for (int i = 1; i <= q; ++ i) {
        ll u, x;
        cin >> u >> x;
        cout << get(u, x) << "\n";
    }
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    srand(time(NULL));

    // file("promote");

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tt = 1;
    // cin >> tt;
    for (int i = 1; i <= tt; ++ i) {
        // cout << "Caso #" << i << "\n";
        solve();
    }

    #ifndef ONLINE_JUDGE
    cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif

    return 0;
} 


// Template functions
ll binmul(ll x, ll ti, ll m) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= m; res %= m;} return res;}
ll binpow(ll x, ll ti, ll m) { ll res = 1;while (ti){if(ti & 1)(res *= x)%=m;(x*=x)%=m;ti >>= 1; x %= m; res %= m;} return res;}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9104 KB Output is correct
3 Correct 3 ms 9308 KB Output is correct
4 Correct 4 ms 9308 KB Output is correct
5 Correct 6 ms 9308 KB Output is correct
6 Correct 4 ms 9308 KB Output is correct
7 Correct 3 ms 9308 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 37400 KB Output is correct
2 Correct 144 ms 36692 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9104 KB Output is correct
3 Correct 3 ms 9308 KB Output is correct
4 Correct 4 ms 9308 KB Output is correct
5 Correct 6 ms 9308 KB Output is correct
6 Correct 4 ms 9308 KB Output is correct
7 Correct 3 ms 9308 KB Output is correct
8 Correct 141 ms 37400 KB Output is correct
9 Correct 144 ms 36692 KB Output is correct
10 Correct 4 ms 9172 KB Output is correct
11 Correct 74 ms 22556 KB Output is correct
12 Correct 218 ms 41132 KB Output is correct
13 Correct 158 ms 34136 KB Output is correct
14 Correct 106 ms 32336 KB Output is correct
15 Correct 81 ms 31180 KB Output is correct