Submission #475893

#	Time	Username	Problem	Language	Result	Execution time	Memory
475893		Jarif_Rahman	Snowball (JOI21_ho_t2)	C++17	33 / 100	2529 ms	20448 KiB

Main

    #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 = 1e18;
    struct segtree{
        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")
      |

• Subtask 1: 33 / 33
• Subtask 2: 0 / 67