oj.uz

Submission #467060

# Submission time Handle Problem Language Result Execution time Memory
467060 2021-08-21T14:04:12 Z mtxas Fountain (eJOI20_fountain) C++14
0 / 100
 1014 ms 37288 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1014 ms 37288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -