제출 #467051

#제출 시각아이디문제언어결과실행 시간메모리
467051mtxasFountain (eJOI20_fountain)C++14
100 / 100
1450 ms43496 KiB
#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'; }

컴파일 시 표준 에러 (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: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';
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...