oj.uz

Submission #529537

# Submission time Handle Problem Language Result Execution time Memory
529537 2022-02-23T06:10:43 Z syl123456 Snowball (JOI21_ho_t2) C++17
100 / 100
 831 ms 16592 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<ll, int> pl;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    ll a[n], b[q];
    for (ll &i : a)
        cin >> i;
    for (ll &i : b)
        cin >> i;
    for (int i = 1; i < q; ++i)
        b[i] += b[i - 1];
    vector<pl> vl, vr;
    vl.emplace_back(0, 0), vr.emplace_back(0, 0);
    for (int i = 0; i < q; ++i) {
        if (b[i] < 0)
            vl.emplace_back(-b[i], i);
        else if (b[i] > 0)
            vr.emplace_back(b[i], i);
    }
    sort(all(vl)), sort(all(vr));
    vector<pl> tmp;
    for (auto [i, j] : vl) {
        while (!tmp.empty() && tmp.back().second >= j)
            tmp.pop_back();
        tmp.emplace_back(i, j);
    }
    vl = tmp, tmp.clear();
    for (auto [i, j] : vr) {
        while (!tmp.empty() && tmp.back().second >= j)
            tmp.pop_back();
        if (tmp.empty() || tmp.back().first < i)
            tmp.emplace_back(i, j);
    }
    vr = tmp;
    ll ans[n]{}, mxl = vl.back().first, mxr = vr.back().first;
    ans[0] += mxl, ans[n - 1] += mxr;
    for (int i = 0; i < n - 1; ++i) {
        if (a[i + 1] - a[i] >= mxl + mxr) {
            ans[i] += mxr, ans[i + 1] += mxl;
            continue;
        }
        ll len = a[i + 1] - a[i];
        ll l = max(0ll, len - mxl), r = min(len, mxr) + 1;
        while (l < r - 1) {
            ll mid = l + r >> 1;
            if (lower_bound(all(vr), pl(mid, -1))->second < lower_bound(all(vl), pl(len - mid + 1, -1))->second)
                l = mid;
            else
                r = mid;
        }
        ans[i] += l, ans[i + 1] += len - l;
    }
    for (ll i : ans)
        cout << i << '\n';
}

Compilation message

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:83:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             ll mid = l + r >> 1;
      |                      ~~^~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 288 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 5 ms 456 KB Output is correct
16 Correct 5 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 324 KB Output is correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 288 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 5 ms 456 KB Output is correct
16 Correct 5 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 43 ms 10108 KB Output is correct
21 Correct 36 ms 10028 KB Output is correct
22 Correct 33 ms 9756 KB Output is correct
23 Correct 41 ms 9632 KB Output is correct
24 Correct 110 ms 9752 KB Output is correct
25 Correct 819 ms 14900 KB Output is correct
26 Correct 828 ms 14924 KB Output is correct
27 Correct 775 ms 14612 KB Output is correct
28 Correct 733 ms 14648 KB Output is correct
29 Correct 674 ms 14376 KB Output is correct
30 Correct 326 ms 13756 KB Output is correct
31 Correct 72 ms 12476 KB Output is correct
32 Correct 51 ms 9424 KB Output is correct
33 Correct 57 ms 1820 KB Output is correct
34 Correct 475 ms 13468 KB Output is correct
35 Correct 517 ms 13584 KB Output is correct
36 Correct 831 ms 14804 KB Output is correct
37 Correct 709 ms 14480 KB Output is correct
38 Correct 753 ms 14604 KB Output is correct
39 Correct 798 ms 14652 KB Output is correct
40 Correct 413 ms 14648 KB Output is correct
41 Correct 37 ms 13860 KB Output is correct
42 Correct 51 ms 8392 KB Output is correct
43 Correct 302 ms 14900 KB Output is correct
44 Correct 38 ms 10664 KB Output is correct
45 Correct 66 ms 14772 KB Output is correct
46 Correct 264 ms 15136 KB Output is correct
47 Correct 218 ms 16184 KB Output is correct
48 Correct 81 ms 16592 KB Output is correct