Submission #988381

#TimeUsernameProblemLanguageResultExecution timeMemory
988381_callmelucianSnowball (JOI21_ho_t2)C++14
100 / 100
1652 ms19776 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 2e5 + 5; ll x[mn], pre[mn], ansLeft[mn], ansRight[mn]; int soon (vector<pl> &vec, ll targ) { auto it = upper_bound(all(vec), make_pair(targ, LLONG_MAX)); if (it == vec.begin()) return INT_MAX; return prev(it)->second; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> x[i]; vector<pl> lVec(1), rVec(1); for (int i = 1; i <= q; i++) { ll w; cin >> w; pre[i] = pre[i - 1] + w; lVec.push_back({pre[i], i}); rVec.push_back({-pre[i], i}); } sort(all(lVec)); sort(all(rVec)); for (int i = 1; i < lVec.size(); i++) { lVec[i].second = min(lVec[i].second, lVec[i - 1].second); rVec[i].second = min(rVec[i].second, rVec[i - 1].second); } for (int i = 1; i <= n; i++) { if (i == 1) { ansLeft[i] = rVec.back().first; continue; } int lg = 63 - __builtin_clzll(x[i] - x[i - 1]); for (ll mask = (1LL << lg); mask; mask >>= 1) { ll tmp = ansLeft[i] | mask, dest = x[i] - tmp; ll need = dest - x[i - 1] + 1; if (soon(lVec, -tmp) < soon(rVec, -need)) ansLeft[i] |= mask; } } for (int i = 1; i <= n; i++) { if (i == n) { ansRight[i] = lVec.back().first; continue; } int lg = 63 - __builtin_clzll(x[i + 1] - x[i]); for (ll mask = (1LL << lg); mask; mask >>= 1) { ll tmp = ansRight[i] | mask, dest = x[i] + tmp; ll need = dest - x[i + 1] - 1; if (soon(rVec, -tmp) < soon(lVec, need)) ansRight[i] |= mask; } } for (int i = 1; i <= n; i++) { //cout << ansLeft[i] << " " << ansRight[i] << " "; cout << ansLeft[i] + ansRight[i] << "\n"; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 1; i < lVec.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...