oj.uz

Submission #400190

# Submission time Handle Problem Language Result Execution time Memory
400190 2021-05-07T14:17:27 Z nvmdava Snowball (JOI21_ho_t2) C++17
0 / 100
 2 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll x[N];
vector<ll> loc;
ll ans[N];

bool sign(ll a, ll b){
    if(a > 0 && b > 0) return 1;
    if(a < 0 && b < 0) return 1;
    return 0;
}

ll get(ll a){
    int l = 1;
    int r = loc.size() - 1;
    if(sign(loc[r], a) && abs(loc[r]) + abs(loc[r - 1]) <= abs(a))
        return abs(loc[r]);
    if(sign(loc[r - 1], a) && abs(loc[r - 1]) + abs(loc[r - 2]) <= abs(a))
        return abs(loc[r - 1]);
    if(r <= 1) return 0;
    while(l != r){
        int m = (l + r) >> 1;
        if(abs(loc[m]) + abs(loc[m - 1]) >= abs(a)){
            r = m;
        } else {
            l = m + 1;
        }
    }
    int m = l;
    if(sign(loc[m], a))
        return abs(a + loc[m - 1]);
    else
        return abs(loc[m - 1]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin>>n>>q;
    for(int i = 1; i <= n; ++i)
        cin>>x[i];
    ll now = 0;
    loc.push_back(0);
    while(q--){
        ll t;
        cin>>t;
        now += t;
        if(now == 0) continue;
        if(sign(now, loc.back())){
            if(abs(now) > abs(loc.back())){
                loc.pop_back();
                loc.push_back(now);
            }
        } else {
            if(loc.size() <= 2 || abs(loc[loc.size() - 2]) < abs(now)){
                loc.push_back(now);
            }
        }
    }

    for(int i = 1; i < n; ++i){
        ans[i] += get(x[i + 1] - x[i]);
        ans[i + 1] += get(x[i] - x[i + 1]);
    }
    ans[n] += get(1'000'000'000'000'000'000);
    ans[1] += get(-1'000'000'000'000'000'000);
    for(int i = 1; i <= n; ++i)
        cout<<ans[i]<<'\n';
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 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 340 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Incorrect 1 ms 332 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 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 340 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Incorrect 1 ms 332 KB Output isn't correct
19 Halted 0 ms 0 KB -