oj.uz

Submission #373490

# Submission time Handle Problem Language Result Execution time Memory
373490 2021-03-04T20:24:45 Z SorahISA Snowball (JOI21_ho_t2) C++17
100 / 100
 118 ms 11756 KB 
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)

template<class T1, class T2>
inline ostream& operator << (ostream& os, pair<T1, T2> p) {
    os << "(" << p.X << "," << p.Y << ")";
    return os;
}

template<class T>
inline ostream& operator << (ostream& os, vector<T> vec) {
    for (auto x : vec) os << x << " ";
    return os;
}

void solve() {
    int n, q; cin >> n >> q;
    
    vector<int> pl(n), wind(q);
    for (auto &x : pl) cin >> x;
    for (auto &x : wind) cin >> x;
    
    vector<pii> maxLR(q+1);
    for (int i = 0, p = 0; i < q; ++i) {
        p += wind[i];
        maxLR[i+1].X = max(maxLR[i].X, -p);
        maxLR[i+1].Y = max(maxLR[i].Y,  p);
    }
    // cout << maxLR << "\n";
    
    vector<pii> snow(n);
    for (int i = 0; i < n-1; ++i) {
        int dist = pl[i+1] - pl[i], lo = 0, hi = q, mi;
        while (lo < hi) {
            mi = lo + hi + 1 >> 1;
            if (maxLR[mi].X + maxLR[mi].Y > dist) hi = mi - 1;
            else lo = mi;
        }
        // cout << dist << " " << lo << "\n";
        if (lo == q) {
            snow[i+1].X = maxLR.back().X;
            snow[i].Y   = maxLR.back().Y;
        }
        else if (maxLR[lo+1].X > maxLR[lo].X) {
            snow[i+1].X = dist - maxLR[lo].Y;
            snow[i].Y   = maxLR[lo].Y;
        }
        else if (maxLR[lo+1].Y > maxLR[lo].Y) {
            snow[i+1].X = maxLR[lo].X;
            snow[i].Y   = dist - maxLR[lo].X;
        }
        // else assert(0);
    }
    snow[0].X = maxLR.back().X, snow[n-1].Y = maxLR.back().Y;
    // cout << snow << "\n";
    
    for (int i = 0; i < n; ++i) cout << snow[i].X + snow[i].Y << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    while (t--) solve();
    
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:51:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |             mi = lo + hi + 1 >> 1;
      |                  ~~~~~~~~^~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 492 KB Output is correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 31 ms 4972 KB Output is correct
21 Correct 30 ms 4972 KB Output is correct
22 Correct 29 ms 4972 KB Output is correct
23 Correct 27 ms 5100 KB Output is correct
24 Correct 34 ms 5740 KB Output is correct
25 Correct 118 ms 11368 KB Output is correct
26 Correct 113 ms 11332 KB Output is correct
27 Correct 108 ms 11116 KB Output is correct
28 Correct 115 ms 11244 KB Output is correct
29 Correct 110 ms 10988 KB Output is correct
30 Correct 105 ms 10564 KB Output is correct
31 Correct 80 ms 10092 KB Output is correct
32 Correct 69 ms 10092 KB Output is correct
33 Correct 11 ms 1516 KB Output is correct
34 Correct 118 ms 11372 KB Output is correct
35 Correct 110 ms 11116 KB Output is correct
36 Correct 112 ms 11372 KB Output is correct
37 Correct 111 ms 11116 KB Output is correct
38 Correct 109 ms 11116 KB Output is correct
39 Correct 109 ms 11244 KB Output is correct
40 Correct 90 ms 11116 KB Output is correct
41 Correct 34 ms 5032 KB Output is correct
42 Correct 68 ms 10092 KB Output is correct
43 Correct 92 ms 11328 KB Output is correct
44 Correct 33 ms 4972 KB Output is correct
45 Correct 76 ms 11244 KB Output is correct
46 Correct 94 ms 11500 KB Output is correct
47 Correct 107 ms 11756 KB Output is correct
48 Correct 98 ms 11500 KB Output is correct