oj.uz

Submission #862048

# Submission time Handle Problem Language Result Execution time Memory
862048 2023-10-17T12:43:32 Z sleepntsheep Snowball (JOI21_ho_t2) C++17
0 / 100
 2 ms 2396 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

ll n, q, x[N], w[N], hi[N], lo[N];

int main()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= q; ++i) cin >> w[i], w[i] += w[i-1], hi[i] = max(hi[i-1], w[i]), lo[i] = min(lo[i-1], w[i]);

    for (int i = 1; i <= n; ++i)
    {
        ll lft= 1e14, rgt=-1e14;
        {
            int l = 1, r = q;
            while (l <= r)
            {
                int y = (l+r)/2;
                if (hi[y] + x[i] > lo[y] + x[i+1]) r = y - 1, rgt = max(rgt, lo[y] + x[i+1]);
                else 
                {
                    l = y + 1, rgt = max(rgt, x[i] + hi[y]);
                    //if (y < q) rgt = max(rgt, lo[y+1] + x[i+1]);
                }
            }
            if (i == n) rgt = x[i] + hi[q];
            l = 1, r = q;
            while (l <= r)
            {
                int y = (l+r)/2;
                if (lo[y] + x[i] < hi[y] + x[i-1]) r = y - 1, lft = min(lft, hi[y] + x[i-1]);
                else 
                {
                    l = y + 1, lft = min(lft, x[i] + lo[y]);
                    //if (y < q) lft = min(lft, hi[y+1] + x[i-1]);
                }
            }
            if (i == 1) lft = x[i] + lo[q];
        }
        cout << rgt - lft << '\n';
    }

    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Incorrect 0 ms 2396 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Incorrect 0 ms 2396 KB Output isn't correct
15 Halted 0 ms 0 KB -