Submission #987782

#	Time	Username	Problem	Language	Result	Execution time	Memory
987782		_callmelucian	Snowball (JOI21_ho_t2)	C++14	33 / 100	2517 ms	31368 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];

void solve (vector<pl> &query, vector<pl> &vec, vector<int> &ans) {
    int it = -1, curAns = INT_MAX;
    for (auto [ub, iQry] : query) {
        while (it + 1 < vec.size() && vec[it + 1].first <= ub)
            curAns = min(curAns, (int)vec[++it].second);
        ans[iQry] = curAns;
    }
}

/*
    main idea: binary search, for every snowball,
    find the nearest position to its right
    such that this snowball reaches that point
    before the snowball right next to it.

    at first glance, time complexity is O(2e5 log 1e12 log 2e5)
    batch process all snowballs for O(2e5 log 1e12) time complexity
*/

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, rVec;

    lVec.push_back({0, 0});
    rVec.push_back({0, 0});
    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));

    /// process left side
    for (ll mask = (1LL << 57); mask; mask >>= 1) {
        vector<pl> lQuery, rQuery;
        vector<int> lAns(n + 1), rAns(n + 1);

        for (int i = 1; i <= n; i++) {
            ll tmp = ansLeft[i] | mask;
            // find the soonest wind for it to reach somewhere <= x[i] - tmp
            lQuery.push_back({-tmp, i});
            if (i > 1) {
                // find the soonest wind for it to reach somewhere >= x[i] - tmp + 1
                ll dest = x[i] - tmp + 1;
                rQuery.push_back({-(dest - x[i - 1]), i - 1});
            }
        }
        sort(all(lQuery)); sort(all(rQuery));

        solve(lQuery, lVec, lAns);
        solve(rQuery, rVec, rAns);

        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                if (lAns[i] != INT_MAX) ansLeft[i] |= mask;
            }
            else {
                if (lAns[i] < rAns[i - 1]) ansLeft[i] |= mask;
            }
        }
    }

    /// process right side
    for (ll mask = (1LL << 57); mask; mask >>= 1) {
        vector<pl> lQuery, rQuery;
        vector<int> lAns(n + 1), rAns(n + 1);

        for (int i = 1; i <= n; i++) {
            ll tmp = ansRight[i] | mask;
            // find the soonest wind for it to reach somewhere >= x[i] + tmp
            rQuery.push_back({-tmp, i});
            if (i < n) {
                // find the soonest wind for it to reach somewhere <= x[i] + tmp - 1
                ll dest = x[i] + tmp - 1;
                lQuery.push_back({dest - x[i + 1], i + 1});
            }
        }
        sort(all(lQuery)); sort(all(rQuery));

        solve(lQuery, lVec, lAns);
        solve(rQuery, rVec, rAns);

        for (int i = 1; i <= n; i++) {
            if (i == n) {
                if (rAns[i] != INT_MAX) ansRight[i] |= mask;
            }
            else {
                if (rAns[i] < lAns[i + 1]) ansRight[i] |= mask;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        //cout << ansLeft[i] << " " << ansRight[i] << " ";
        cout << ansRight[i] + ansLeft[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >&, std::vector<int>&)':
Main.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [ub, iQry] : query) {
      |               ^
Main.cpp:19: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]
   19 |         while (it + 1 < vec.size() && vec[it + 1].first <= ub)
      |                ~~~~~~~^~~~~~~~~~~~

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