oj.uz

Submission #475851

# Submission time Handle Problem Language Result Execution time Memory
475851 2021-09-24T09:28:20 Z Jarif_Rahman Snowball (JOI21_ho_t2) C++17
33 / 100
 2436 ms 24516 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

const ll inf = 1e13;
struct segtree{
    const ll inf = 1e18;
    struct node{
        ll sm, mx, mn;
        node(){
            sm = 0, mx = -1e18, mn = 1e18;
        }
        node(ll x){
            sm = x, mx = x, mn = x;
        }
        node operator+(node a){
            node rt;
            rt.sm = sm+a.sm;
            rt.mx = max(mx, a.mx);
            rt.mn = min(mn, a.mn);
            return rt;
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.resize(k, node());
    }
    void upd(int in, ll x){
        in+=k/2;
        v[in] = node(x);
        in/=2;
        while(in > 0){
            v[in] = v[2*in]+v[2*in+1];
            in/=2;
        }
    }
    int first_atleast(int nd, int a, int b, ll x){
        if(v[nd].mx < x) return -1;
        if(a == b) return a;
        int md = (a+b)/2;
        if(v[2*nd].mx < x) return first_atleast(2*nd+1, md+1, b, x);
        else return first_atleast(2*nd, a, md, x);
    }
    int first_atleast(ll x){
        return first_atleast(1, 0, k/2-1, x);
    }
    int first_atmost(int nd, int a, int b, ll x){
        if(v[nd].mn > x) return -1;
        if(a == b) return a;
        int md = (a+b)/2;
        if(v[2*nd].mn > x) return first_atmost(2*nd+1, md+1, b, x);
        else return first_atmost(2*nd, a, md, x);
    }
    int first_atmost(ll x){
        return first_atmost(1, 0, k/2-1, x);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    vector<ll> v(n);
    for(ll &x: v) cin >> x;

    vector<ll> w(q);
    for(ll &x: w) cin >> x;
    vector<ll> sum(q+1);
    sum[0] = 0;
    for(int i = 0; i < q; i++) sum[i+1] = sum[i]+w[i];
    segtree seg(q+1);
    for(int i = 0; i < q+1; i++) seg.upd(i, sum[i]);

    vector<ll> ans(n, 0);

    for(int i = 0; i < n; i++){
        
        ll a = -inf, b = v[i];
        if(i != 0) a = v[i-1];
        while(a < b){
            ll md = (a+b);
            if(md >= 0) md/=2;
            else md/=2, md--;
            int x = seg.first_atmost(md-v[i]);
            if(x == -1){
                a = md+1;
                continue;
            }
            if(i != 0 && seg.first_atleast(md+1-v[i-1]) != -1 && seg.first_atleast(md+1-v[i-1]) < x){
                a = md+1;
                continue;
            }
            b = md;
        }
        ans[i]+=v[i]-a;

        a = v[i], b = inf;
        if(i != n-1) b = v[i+1];
        while(a < b){
            ll md = (a+b+1)/2;
            int x = seg.first_atleast(md-v[i]);
            if(x == -1){
                b = md-1;
                continue;
            }
            if(i != n-1 && seg.first_atmost(md-1-v[i+1]) != -1 && seg.first_atmost(md-1-v[i+1]) < x){
                b = md-1;
                continue;
            }
            a = md;
        }
        ans[i]+=a-v[i];

    }

    for(ll x: ans) cout << x << "\n";
}

Compilation message

Main.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("O3")
      | 
Main.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 14 ms 516 KB Output is correct
5 Correct 12 ms 508 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 9 ms 460 KB Output is correct
8 Correct 8 ms 460 KB Output is correct
9 Correct 7 ms 452 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 0 ms 308 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 14 ms 516 KB Output is correct
16 Correct 16 ms 520 KB Output is correct
17 Correct 12 ms 516 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 2 ms 576 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 14 ms 516 KB Output is correct
5 Correct 12 ms 508 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 9 ms 460 KB Output is correct
8 Correct 8 ms 460 KB Output is correct
9 Correct 7 ms 452 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 0 ms 308 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 14 ms 516 KB Output is correct
16 Correct 16 ms 520 KB Output is correct
17 Correct 12 ms 516 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 2 ms 576 KB Output is correct
20 Correct 48 ms 16780 KB Output is correct
21 Correct 46 ms 16848 KB Output is correct
22 Correct 55 ms 16776 KB Output is correct
23 Correct 76 ms 16708 KB Output is correct
24 Correct 323 ms 17220 KB Output is correct
25 Correct 2436 ms 21456 KB Output is correct
26 Correct 2417 ms 24092 KB Output is correct
27 Correct 2301 ms 23776 KB Output is correct
28 Correct 2244 ms 23864 KB Output is correct
29 Correct 2264 ms 23428 KB Output is correct
30 Correct 1128 ms 22864 KB Output is correct
31 Correct 177 ms 22244 KB Output is correct
32 Correct 85 ms 22344 KB Output is correct
33 Correct 175 ms 3012 KB Output is correct
34 Correct 2149 ms 24516 KB Output is correct
35 Correct 2149 ms 23984 KB Output is correct
36 Correct 2426 ms 24260 KB Output is correct
37 Correct 2253 ms 23872 KB Output is correct
38 Correct 2248 ms 23816 KB Output is correct
39 Correct 2167 ms 24020 KB Output is correct
40 Correct 1322 ms 24004 KB Output is correct
41 Incorrect 54 ms 18504 KB Output isn't correct
42 Halted 0 ms 0 KB -