Submission #467063

# Submission time Handle Problem Language Result Execution time Memory
467063 2021-08-21T14:14:05 Z mtxas Fountain (eJOI20_fountain) C++14
100 / 100
374 ms 38724 KB
#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

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';
      |     ^~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 260 ms 35172 KB Output is correct
2 Correct 274 ms 33052 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 260 ms 35172 KB Output is correct
9 Correct 274 ms 33052 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 116 ms 21108 KB Output is correct
12 Correct 374 ms 38448 KB Output is correct
13 Correct 262 ms 38724 KB Output is correct
14 Correct 214 ms 38252 KB Output is correct
15 Correct 183 ms 38212 KB Output is correct