Submission #467063

#	Time	Username	Problem	Language	Result	Execution time	Memory
467063		mtxas	Fountain (eJOI20_fountain)	C++14	100 / 100	374 ms	38724 KiB

fountain

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define mfsadfp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mii map<int, int>
#define all(a) a.begin(), a.end()
#define _fre() freopen("input.txt", "r", stdin)
#define turbo() cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
#define sz(x) ((int)x.size())
#define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
#define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
#define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
#define _forn(a, b, c) for(int (a) = (b); (a) > (c); (a)--)
using namespace std;
#define int ll
/***********************************************************************************
                                 STRUCTS
************************************************************************************/

/***********************************************************************************
                                VARIABLES
************************************************************************************/
const int maxn = 2e5+10, inf = 1e16, mlog = 20;
int n, Q;
int C[maxn], D[maxn], R[maxn], V[maxn];
int p[maxn];
int upCost[maxn][mlog];
int upId[maxn][mlog];
/***********************************************************************************
                                FUNCTIONS
************************************************************************************/
void calcLifts(){
    _foreq(i, 1, n+1) upId[i][0] = p[i];
    _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
        upId[i][j] = upId[upId[i][j-1]][j-1];
    _foreq(i, 1, n+1) upCost[i][0] = C[i];
    _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
        upCost[i][j] = upCost[i][j-1] + upCost[upId[i][j-1]][j-1];
}
int query(int v, int w){
    w--; // cost <= w
    _forneq(j, mlog-1, 0){
        int cost = upCost[v][j];
        if(cost<=w){
            w-= cost;
            v = upId[v][j];
        }
    }
    return v%(n+1);
}
void findParents(){
    p[n+1] = n+1;
    stack<pii> stek; // <val, id>
    stek.push({D[n+1], n+1});
    _forneq(i, n, 1){
        while(stek.top().fi <= D[i]) stek.pop();
        p[i] = stek.top().se;
        stek.push({D[i], i});
    }
}
/***********************************************************************************
                                  MAIN
************************************************************************************/
signed main(){
   // _fre();
    turbo();
    cin>>n>>Q;
    _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
    findParents();
    calcLifts();
    _for(i, 0, Q) cin>>R[i]>>V[i];
    _for(g, 0, Q) cout<<query(R[g], V[g])<<'\n';

}

Compilation message (stderr)

fountain.cpp: In function 'void calcLifts()':
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:40:5: note: in expansion of macro '_foreq'
   40 |     _foreq(i, 1, n+1) upId[i][0] = p[i];
      |     ^~~~~~
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:41:5: note: in expansion of macro '_foreq'
   41 |     _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
      |     ^~~~~~
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:41:26: note: in expansion of macro '_foreq'
   41 |     _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
      |                          ^~~~~~
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:43:5: note: in expansion of macro '_foreq'
   43 |     _foreq(i, 1, n+1) upCost[i][0] = C[i];
      |     ^~~~~~
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:44:5: note: in expansion of macro '_foreq'
   44 |     _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
      |     ^~~~~~
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:44:26: note: in expansion of macro '_foreq'
   44 |     _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
      |                          ^~~~~~
fountain.cpp: In function 'long long int query(long long int, long long int)':
fountain.cpp:19:34: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
      |                                  ^
fountain.cpp:49:5: note: in expansion of macro '_forneq'
   49 |     _forneq(j, mlog-1, 0){
      |     ^~~~~~~
fountain.cpp: In function 'void findParents()':
fountain.cpp:19:34: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   19 | #define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
      |                                  ^
fountain.cpp:62:5: note: in expansion of macro '_forneq'
   62 |     _forneq(i, n, 1){
      |     ^~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:75:5: note: in expansion of macro '_foreq'
   75 |     _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
      |     ^~~~~~
fountain.cpp:18:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                         ^~~
fountain.cpp:75:5: note: in expansion of macro '_foreq'
   75 |     _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
      |     ^~~~~~
fountain.cpp:75:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |     _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
      |                                      ^
fountain.cpp:17:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
fountain.cpp:78:5: note: in expansion of macro '_for'
   78 |     _for(i, 0, Q) cin>>R[i]>>V[i];
      |     ^~~~
fountain.cpp:17:31: warning: unnecessary parentheses in declaration of 'g' [-Wparentheses]
   17 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
fountain.cpp:79:5: note: in expansion of macro '_for'
   79 |     _for(g, 0, Q) cout<<query(R[g], V[g])<<'\n';
      |     ^~~~

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