oj.uz

답안 #438697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438697 2021-06-28T13:35:48 Z JovanB Snowball (JOI21_ho_t2) C++17
100 / 100
 614 ms 16952 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXN = 200000;

ll levo[MAXN+5];
ll desno[MAXN+5];
ll x[MAXN+5];

ll pre[MAXN+5], minpref[MAXN+5], maxpref[MAXN+5];

const ll INF = 2000000000000000000LL;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> x[i];
    }
    for(int i=1; i<=m; i++){
        cin >> pre[i];
        pre[i] += pre[i-1];
        maxpref[i] = max(maxpref[i-1], pre[i]);
        minpref[i] = min(minpref[i-1], pre[i]);
    }
    for(int i=1; i<=n; i++) levo[i] = desno[i] = x[i];
    x[0] = -INF;
    x[n+1] = INF;
    desno[0] = -INF;
    for(int i=1; i<=n; i++){
        ll l = x[i]+1, r = min(x[i+1], maxpref[m] + x[i]), res = x[i];
        while(l <= r){
            ll mid = (l+r)/2;
            int ind1 = lower_bound(maxpref+1, maxpref+1+m, mid - x[i]) - maxpref;
            if(ind1 > m){
                r = mid-1;
                continue;
            }
            ll x2 = minpref[ind1];
            if(x[i+1] + x2 >= mid){
                l = mid+1;
                res = mid;
            }
            else r = mid-1;
        }
        desno[i] = res;
    }
    for(int i=1; i<=n; i++){
        levo[i] = max(x[i] + minpref[m], desno[i-1]);
        cout << desno[i] - levo[i] << "\n";
    }
    return 0;
}

Subtask #1
33.0 / 33.0

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

Subtask #2
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 420 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 5 ms 460 KB Output is correct
16 Correct 4 ms 460 KB Output is correct
17 Correct 4 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 36 ms 7036 KB Output is correct
21 Correct 36 ms 6916 KB Output is correct
22 Correct 37 ms 6744 KB Output is correct
23 Correct 47 ms 6544 KB Output is correct
24 Correct 97 ms 7264 KB Output is correct
25 Correct 610 ms 14964 KB Output is correct
26 Correct 586 ms 14892 KB Output is correct
27 Correct 550 ms 14496 KB Output is correct
28 Correct 537 ms 14664 KB Output is correct
29 Correct 451 ms 14228 KB Output is correct
30 Correct 279 ms 13632 KB Output is correct
31 Correct 83 ms 13032 KB Output is correct
32 Correct 81 ms 13252 KB Output is correct
33 Correct 49 ms 1816 KB Output is correct
34 Correct 516 ms 15248 KB Output is correct
35 Correct 534 ms 14764 KB Output is correct
36 Correct 613 ms 14916 KB Output is correct
37 Correct 614 ms 14728 KB Output is correct
38 Correct 560 ms 14492 KB Output is correct
39 Correct 519 ms 14724 KB Output is correct
40 Correct 221 ms 14680 KB Output is correct
41 Correct 36 ms 7664 KB Output is correct
42 Correct 78 ms 13220 KB Output is correct
43 Correct 200 ms 16464 KB Output is correct
44 Correct 36 ms 7516 KB Output is correct
45 Correct 170 ms 14736 KB Output is correct
46 Correct 203 ms 16636 KB Output is correct
47 Correct 214 ms 16880 KB Output is correct
48 Correct 96 ms 16952 KB Output is correct