제출 #464249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464249		gesgha	Fountain (eJOI20_fountain)	C++17	0 / 100	886 ms	42692 KiB

fountain

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