oj.uz

답안 #624325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624325 2022-08-07T19:48:27 Z Ronin13 Snowball (JOI21_ho_t2) C++14
100 / 100
 579 ms 12580 KB 
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 200005;
const ll linf = 5e18 + 1;
ll mn[NMAX], mx[NMAX];


int main(){
    int n, q; cin >> n >> q;
    ll a[n + 2];
    a[0] = -linf;
    a[n + 1] = linf;
    for(int i =1; i <= n; i++) cin >> a[i];
    ll pref[q + 1];
    mn[0] = 0;
    mx[0] = 0;
    pref[0] = 0;
    for(int i = 1; i <= q; i++){
        ll x; cin >> x;
        pref[i] = pref[i - 1] + x;
        mx[i] = max(mx[i - 1], pref[i]);
        mn[i] = min(mn[i - 1], pref[i]);
        //cout << mx[i] << ' ' << mn[i] << "\n";
    }
    ll ans[n + 2];
    for(int i = 0; i <= n + 1; i++) ans[i] = 0;
    for(int i = 1; i <= n + 1; i++){
        ll l = 0, r = a[i] - a[i - 1] + 1;
        while(l + 1 < r){
            ll mid = (l + r) / 2;
            ll l1 = -1, r1 = q + 1;
            while(l1 + 1 < r1){
                ll mid1 = l1 + r1; mid1 /= 2;
                if(mn[mid1] <= -mid) r1 = mid1;
                else l1 = mid1;
            }
           // cout << 1;

            if(r1 == q + 1){
                r = mid;
                continue;
            }
            if(mx[r1] <= a[i] - a[i - 1] - mid) l = mid;
            else {r = mid;}
        }
        //cout << l << "\n";
        ans[i - 1] += min(mx[q], a[i] - a[i - 1] - l);
        ans[i] += l;
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 2 ms 340 KB Output is correct

Subtask #2
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 83 ms 6256 KB Output is correct
21 Correct 73 ms 6188 KB Output is correct
22 Correct 68 ms 6208 KB Output is correct
23 Correct 68 ms 6176 KB Output is correct
24 Correct 135 ms 6720 KB Output is correct
25 Correct 579 ms 10928 KB Output is correct
26 Correct 567 ms 10920 KB Output is correct
27 Correct 543 ms 10832 KB Output is correct
28 Correct 521 ms 10744 KB Output is correct
29 Correct 523 ms 10536 KB Output is correct
30 Correct 371 ms 10160 KB Output is correct
31 Correct 163 ms 9744 KB Output is correct
32 Correct 143 ms 9676 KB Output is correct
33 Correct 48 ms 1612 KB Output is correct
34 Correct 534 ms 11012 KB Output is correct
35 Correct 541 ms 10668 KB Output is correct
36 Correct 569 ms 10916 KB Output is correct
37 Correct 571 ms 10660 KB Output is correct
38 Correct 565 ms 10672 KB Output is correct
39 Correct 555 ms 10676 KB Output is correct
40 Correct 387 ms 10688 KB Output is correct
41 Correct 96 ms 6236 KB Output is correct
42 Correct 247 ms 11300 KB Output is correct
43 Correct 275 ms 12496 KB Output is correct
44 Correct 93 ms 7508 KB Output is correct
45 Correct 414 ms 12324 KB Output is correct
46 Correct 263 ms 12528 KB Output is correct
47 Correct 281 ms 12564 KB Output is correct
48 Correct 278 ms 12580 KB Output is correct