Submission #475889

#TimeUsernameProblemLanguageResultExecution timeMemory
475889Jarif_RahmanSnowball (JOI21_ho_t2)C++17
33 / 100
2502 ms21116 KiB
#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);
            if(md >= 0) md++, md/=2;
            else md/=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 (stderr)

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")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...