Submission #988381

#	Time	Username	Problem	Language	Result	Execution time	Memory
988381		_callmelucian	Snowball (JOI21_ho_t2)	C++14	100 / 100	1652 ms	19776 KiB

Main

#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++) {
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67