Submission #1019367

#TimeUsernameProblemLanguageResultExecution timeMemory
1019367underwaterkillerwhaleIntercastellar (JOI22_ho_t1)C++17
100 / 100
291 ms70312 KiB
#include <bits/stdc++.h> #define se second #define fs first #define mp make_pair #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 2e5 + 7; const int Mod =1e9 + 7; const int szBL = 916; const ll INF = 1e18; const int BASE = 137; struct Data { ll a, b, c; }; int n, Q; ll a[N]; ll dp[N]; vector<ll> Val, g; void solution () { cin >> n; rep (i, 1, n) { cin >> a[i]; ll X = a[i]; while (X > 0 && X % 2 == 0) { Val.push_back(X); X /= 2; } Val.push_back(X); } sort (ALL(Val)); Val.resize(unique(ALL(Val)) - Val.begin()); g.resize(SZ(Val) + 1, 0); // iter (&id, Val) cout << id <<"\n"; rep (i, 0, SZ(Val) - 1) { ll cur = Val[i]; if (cur & 1) g[i] = 1; else { g[i] = g[lower_bound(ALL(Val), cur / 2) - Val.begin()] * 2; // cout << cur<<" "<<g[5]<<" "<<lower_bound(ALL(Val), cur / 2) - Val.begin()<<"\n"; } } rep (i, 1, n) { dp[i] = dp[i - 1] + g[lower_bound(ALL(Val), a[i]) - Val.begin()]; // cout << g[lower_bound(ALL(Val), a[i]) - Val.begin()]<<","<<dp[i] <<" "; } // cout<<"\n"; // return; int ptr = 0; cin >> Q; rep (i, 1, Q) { ll X; cin >> X; while (ptr < n - 1 && dp[ptr + 1] < X) ++ptr; ll cur = a[ptr + 1]; ll delta = X - dp[ptr]; while (cur > 0 && cur % 2 == 0) { cur /= 2; } cout << cur <<"\n"; } } #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // file ("c"); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* 1 2 */

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:75:12: warning: unused variable 'delta' [-Wunused-variable]
   75 |         ll delta = X - dp[ptr];
      |            ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...