oj.uz

Submission #467051

# Submission time Handle Problem Language Result Execution time Memory
467051 2021-08-21T13:20:32 Z mtxas Fountain (eJOI20_fountain) C++14
100 / 100
 1450 ms 43496 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);
}
/***********************************************************************************
                                  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;
    _foreq(i, 1, n+1) upd(i, D[i]);
    p[n+1] = n+1;
    _foreq(i, 1, n) p[i] = findParent(i);
    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 '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:107:5: note: in expansion of macro '_foreq'
  107 |     _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:107:5: note: in expansion of macro '_foreq'
  107 |     _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
      |     ^~~~~~
fountain.cpp:107:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  107 |     _foreq(i, 1, n) cin>>D[i]>>C[i]; D[n+1] = inf; C[n+1] = 0;
      |                                      ^
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:108:5: note: in expansion of macro '_foreq'
  108 |     _foreq(i, 1, n+1) upd(i, D[i]);
      |     ^~~~~~
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:110:5: note: in expansion of macro '_foreq'
  110 |     _foreq(i, 1, n) p[i] = findParent(i);
      |     ^~~~~~
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:112:5: note: in expansion of macro '_for'
  112 |     _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:113:5: note: in expansion of macro '_for'
  113 |     _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 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 4 ms 756 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 36640 KB Output is correct
2 Correct 1035 ms 34212 KB Output is correct

Subtask #3
40.0 / 40.0

# 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 2 ms 588 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 4 ms 756 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 1046 ms 36640 KB Output is correct
9 Correct 1035 ms 34212 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 377 ms 21832 KB Output is correct
12 Correct 1450 ms 39976 KB Output is correct
13 Correct 938 ms 43496 KB Output is correct
14 Correct 560 ms 42688 KB Output is correct
15 Correct 431 ms 42992 KB Output is correct