oj.uz

Submission #467062

# Submission time Handle Problem Language Result Execution time Memory
467062 2021-08-21T14:04:47 Z mtxas Fountain (eJOI20_fountain) C++14
100 / 100
 1401 ms 39900 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 t[maxn<<1];
int N;
int upCost[maxn][mlog];
int upId[maxn][mlog];
/***********************************************************************************
                                FUNCTIONS
************************************************************************************/
void upd(int p, int val){
    for(t[p+=N] = val; p>1; p>>=1)
        t[p>>1] = max(t[p], t[p^1]);
}
int q(int l, int r){
    int ans = 0; r++;
    for(l+=N, r+=N; l<r; l>>=1, r>>=1){
        if(r&1) ans = max(ans, t[--r]);
        if(l&1) ans = max(ans, t[l++]);
    }
    return ans;
}
int findParent(int i){
    int L = 1, R = n-i+1, k = (L+R)/2;
    int d = D[i];
    while(L<=R){
        int res = q(i+1, i+k);
        if(res <= d) L = k+1;
        else R = k-1;
        k = (L+R)/2;
    }
    return i + L;
}
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 jumpCost(int v, int h){
    int ans = 0;
    _foreq(i, 0, 31)
        if((h>>i)&1){
            ans += upCost[v][i];
            v = upId[v][i];
        }
    return ans;
}
int jumpId(int v, int h){
    _foreq(i, 0, 31)
        if((h>>i)&1){
            v = upId[v][i];
        }
    return v;
}
int query(int v, int w){
    w--;
    if(jumpCost(v, 1) > w) return v;
    int L = 1, R = n+1, k = (L+R)/2;
    while(L<=R){
        int cost = jumpCost(v, k);
        if(cost > w) R = k-1;
        else L = k+1;
        k = (L+R)/2;
    }
    return jumpId(v, R)%(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;
       // cout<<"p["<<i<<"] = "<<p[i]<<endl;
        stek.push({D[i], i});
    }
}
/***********************************************************************************
                                  MAIN
************************************************************************************/
signed main(){
   // _fre();
    turbo();
    cin>>n>>Q; N = n+3;
    _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:65:5: note: in expansion of macro '_foreq'
   65 |     _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:66:5: note: in expansion of macro '_foreq'
   66 |     _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:66:26: note: in expansion of macro '_foreq'
   66 |     _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:68:5: note: in expansion of macro '_foreq'
   68 |     _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:69:5: note: in expansion of macro '_foreq'
   69 |     _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:69:26: note: in expansion of macro '_foreq'
   69 |     _foreq(j, 1, mlog-1) _foreq(i, 1, n+1)
      |                          ^~~~~~
fountain.cpp: In function 'long long int jumpCost(long long int, long long int)':
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:74:5: note: in expansion of macro '_foreq'
   74 |     _foreq(i, 0, 31)
      |     ^~~~~~
fountain.cpp: In function 'long long int jumpId(long long int, long long int)':
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:82:5: note: in expansion of macro '_foreq'
   82 |     _foreq(i, 0, 31)
      |     ^~~~~~
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:104:5: note: in expansion of macro '_forneq'
  104 |     _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:118:5: note: in expansion of macro '_foreq'
  118 |     _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:118:5: note: in expansion of macro '_foreq'
  118 |     _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
      |     ^~~~~~
fountain.cpp:118:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  118 |     _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:121:5: note: in expansion of macro '_for'
  121 |     _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:122:5: note: in expansion of macro '_for'
  122 |     _for(g, 0, Q) cout<<query(R[g], V[g])<<'\n';
      |     ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 36260 KB Output is correct
2 Correct 1194 ms 34384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 1058 ms 36260 KB Output is correct
9 Correct 1194 ms 34384 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 379 ms 22376 KB Output is correct
12 Correct 1401 ms 39720 KB Output is correct
13 Correct 979 ms 39900 KB Output is correct
14 Correct 503 ms 39584 KB Output is correct
15 Correct 293 ms 39588 KB Output is correct