Submission #1133045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133045		patgra	Fountain (eJOI20_fountain)	C++20	100 / 100	312 ms	32344 KiB

fountain

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)

#define ll long long

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

using namespace std;

constexpr int maxn = 1e5 + 7, maxLog = 18, inf = 1e9 + 7, treeBase = 1 << maxLog;
int n, q;
int diameter[maxn], capacity[maxn];
pair<ll, int> jp[maxn][maxLog];
int nxt[maxn];
int tree[2 * treeBase];

void input() {
    scanf("%d%d", &n, &q);
    rep(i, 1, n + 1) scanf("%d%d", diameter + i, capacity + i);
}

void initTree() {
    rep(i, 1, n + 1) tree[treeBase + i] = diameter[i];
    tree[treeBase + n + 1] = inf;
    repD(i, treeBase - 1, 0) tree[i] = max(tree[2 * i], tree[2 * i + 1]);
}
int queryTree(int i) {
    int baseDiameter = diameter[i];
    i += treeBase + 1;
    if (tree[i] > baseDiameter) return i - treeBase;
    while (i > 1 && (i % 2 == 1 || tree[i + 1] <= baseDiameter)) i /= 2;
    if (i > treeBase) return i + 1 - treeBase;
    i = (i + 1) * 2;
    while (i < treeBase) i += tree[i] <= baseDiameter, i *= 2;
    i += tree[i] <= baseDiameter;
    return i - treeBase;
}
void calcNext() {
    initTree();
    rep(i, 1, n + 1) nxt[i] = queryTree(i), nxt[i] = (nxt[i] == n + 1) ? 0 : nxt[i];
    DEBUG {
        DC << "nxt: ";
        rep(i, 1, n + 1) DC << nxt[i] << ' '; DC << eol;
    }
}

void initJP() {
    calcNext();
    rep(i, 1, n + 1) jp[i][0] = {capacity[i], nxt[i]};
    rep(k, 1, maxLog) rep(i, 1, n + 1) jp[i][k].first = jp[i][k - 1].first + jp[jp[i][k - 1].second][k - 1].first, jp[i][k].second = jp[jp[i][k - 1].second][k - 1].second;
}

int query(int start, int litres) {
    repD(k, maxLog - 1, -1) if (litres > jp[start][k].first) litres -= jp[start][k].first, start = jp[start][k].second;
    return start;
}

void processQueries() {
    int a, b;
    rep(i, 0, q) scanf("%d%d", &a, &b), printf("%d\n", query(a, b));
}

int main() {
    input();
    initJP();
    processQueries();
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'void input()':
fountain.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:26:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     rep(i, 1, n + 1) scanf("%d%d", diameter + i, capacity + i);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp: In function 'void processQueries()':
fountain.cpp:67:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     rep(i, 0, q) scanf("%d%d", &a, &b), printf("%d\n", query(a, b));
      |                  ~~~~~^~~~~~~~~~~~~~~~

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