Submission #839012

#	Time	Username	Problem	Language	Result	Execution time	Memory
839012		EntityPlantt	Fountain (eJOI20_fountain)	C++14	60 / 100	1565 ms	43340 KiB

fountain

#define ONLINE_JUDGE
#include <iostream>
#include <vector>
using namespace std;
typedef int64_t ll;
const ll mxn = 100005, mxlogn = 18;
vector <ll> falling, children[mxn];
ll n, q, i, j, diameter[mxn], parent[mxn][mxlogn], cost[mxn][mxlogn], cost0[mxn], l, r, m, a;
ll jumpCost(ll index, ll len) {
    ll r = 0, start = index;
    for (ll k = 0; k < mxlogn; k++) {
        if (index < 0) return cost0[start];
        if (len & 1 << k) {
            r += cost[index][k];
            index = parent[index][k];
        }
    }
    return r;
}
ll jump(ll index, ll len) {
    for (ll k = 0; k < mxlogn; k++) {
        if (index < 0) return -1;
        if (len & 1 << k) index = parent[index][k];
    }
    return index;
}
void calcCost0(ll node, ll co) {
    cost0[node] = co;
    for (ll &x : children[node]) calcCost0(x, co + cost[x][0]);
}
int main() {
    cin >> n >> q;
    for (i = 0; i < n; i++) {
        cin >> diameter[i] >> cost[i][0];
        for (j = 0; j < mxlogn; j++) parent[i][j] = -1;
    }
    #ifndef ONLINE_JUDGE
    cout << "> Creating tree\n";
    #endif
    for (i = 0; i < n; i++) {
        #ifndef ONLINE_JUDGE
        cout << "| i = " << i << ", falling = [";
        if (falling.empty()) cout << ']';
        else {
            for (ll &x : falling) cout << x << ", ";
            cout << "\b\b]";
        }
        #endif
        for (j = falling.size() - 1LL; j >= 0; j--) {
            if (diameter[falling[j]] < diameter[i]) {
                parent[falling[j]][0] = i;
                children[i].push_back(falling[j]);
                falling.erase(falling.begin() + j);
            }
        }
        #ifndef ONLINE_JUDGE
        cout << ", finished\n";
        #endif
        falling.push_back(i);
    }
    for (ll &x : falling) calcCost0(x, cost[x][0]);
    #ifndef ONLINE_JUDGE
    cout << "cost0 =";
    for (i = 0; i < n; i++) cout << ' ' << cost0[i];
    cout << "\n> Creating sparse tables\n";
    #endif
    for (j = 1; j < mxlogn; j++) {
        #ifndef ONLINE_JUDGE
        printf("| %7lldth parent", 1LL << j);
        #endif
        for (i = 0; i < n; i++) {
            if (parent[i][j - 1] >= 0 && parent[parent[i][j - 1]][j - 1] >= 0) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
                cost[i][j] = cost[i][j - 1] + cost[parent[i][j - 1]][j - 1];
            }
            else {
                cost[i][j] = cost0[i];
            }
            #ifndef ONLINE_JUDGE
            printf(" %4lld", parent[i][j]);
            #endif
        }
        #ifndef ONLINE_JUDGE
        printf("\n| %7lldth cost  ", 1LL << j);
        for (i = 0; i < n; i++) {
            printf(" %4lld", cost[i][j]);
        }
        cout << '\n';
        #endif
    }
    #ifndef ONLINE_JUDGE
    cout << "Starting queries\n";
    #endif
    while (q--) {
        cin >> i >> j;
        l = 0; r = n + 5; i--;
        while (l <= r) {
            m = l + r >> 1;
            #ifndef ONLINE_JUDGE
            printf("| l = %lld, r = %lld, m = %lld, cost = %lld\n", l, r, m, jumpCost(i, m));
            #endif
            if (jumpCost(i, m) >= j) r = m - 1;
            else { a = m; l = m + 1; }
        }
        cout << jump(i, a) + 1 << '\n';
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:98:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             m = l + r >> 1;
      |                 ~~^~~

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