oj.uz

Submission #464250

# Submission time Handle Problem Language Result Execution time Memory
464250 2021-08-12T15:32:23 Z gesgha Fountain (eJOI20_fountain) C++17
100 / 100
 1132 ms 40164 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fr(x, l, r) for(int x = l; x <= r; x++)
#define rf(x, l, r) for(int x = l; x >= r; x--)
#define fe(x, y) for(auto& x : y)

#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define pw(x) (ull(1) << ull(x))
#define all(x) (x).begin(),x.end()
#define sz(x) (int)x.size()
#define mt make_tuple
#define ve vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <ld,ld> pld;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template<typename T>
bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T>
bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; }

const ll inf = 1e18;
const int intf = 1e9;
const ll mod = 1e9 + 7;
const ld eps = 0.00000001;
const ll N  = 2e5 + 5;

ll d[N], c[N], p[N], lft[N], b[26][N];

ve <ll> g[N];


void dfs(int u, int p = 0){

    lft[u] = lft[p] + c[u];
//    cout << lft[p] << " " << c[u] << " "  << u << " " << lft[u] << endl;
    b[0][u] = p;
    fr(i, 1, 25){
        b[i][u] = b[i - 1][b[i - 1][u]];
    }

    fe(v, g[u]){
        dfs(v, u);
    }
}


int main(){

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt","w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#else
//    freopen("mountains.in", "r", stdin);
//    freopen("mountains.out","w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int n, q;
    cin >> n >> q;
    ve <ll> steck;
    fr(i, 1, n){
        cin >> d[i] >> c[i];
    }
    fr(i, 1, n){
        while(sz(steck) && d[steck[sz(steck) - 1]] < d[i]){
            p[steck[sz(steck) - 1]] = i;
            g[i].pb(steck[sz(steck) - 1]);
            steck.pop_back();
        }
        steck.pb(i);
    }
    while(sz(steck)){
        g[0].pb(steck[sz(steck) - 1]);
        steck.pop_back();
    }


    dfs(0, 0);
    while(q--){
        int r, c;
        cin >> r >> c;
        int u = r;
//        lft = left[r];
        rf(i, 25, 0){
//            cout << lft[u] << " " << lft[b[i][r]] << " " << b[i][r] << endl;
            if(lft[u] - lft[p[b[i][r]]] < c){
                r = b[i][r];
            }

        }
        if(c > lft[u] - lft[p[r]]) cout <<p[r] << endl;
        else cout << r << endl;
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 6 ms 5324 KB Output is correct
4 Correct 7 ms 5452 KB Output is correct
5 Correct 8 ms 5452 KB Output is correct
6 Correct 8 ms 5452 KB Output is correct
7 Correct 8 ms 5416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 34220 KB Output is correct
2 Correct 818 ms 35104 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 6 ms 5324 KB Output is correct
4 Correct 7 ms 5452 KB Output is correct
5 Correct 8 ms 5452 KB Output is correct
6 Correct 8 ms 5452 KB Output is correct
7 Correct 8 ms 5416 KB Output is correct
8 Correct 617 ms 34220 KB Output is correct
9 Correct 818 ms 35104 KB Output is correct
10 Correct 8 ms 5452 KB Output is correct
11 Correct 412 ms 22036 KB Output is correct
12 Correct 1132 ms 40164 KB Output is correct
13 Correct 1022 ms 36192 KB Output is correct
14 Correct 1008 ms 34848 KB Output is correct
15 Correct 932 ms 35136 KB Output is correct