Submission #794314

#	Time	Username	Problem	Language	Result	Execution time	Memory
794314		79brue	Triangle Collection (CCO23_day2problem3)	C++17	25 / 25	2083 ms	26952 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick{
    int n;
    ll tree[200002];

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) tree[i] = 0;
    }

    void add(int x, ll y){
        while(x<=n){
            tree[x] += y;
            x += x&-x;
        }
    }

    ll sum(int x){
        x = min(x, n);
        ll ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    ll sum(int l, int r){
        r = min(n, r), l = max(l, 1);
        if(l>r) return 0;
        return sum(r) - sum(l-1);
    }
} fenwick, halfFenwick;

struct sumSegTree{
    ll tree[1<<20];

    void init(int i, int l, int r, ll *A){
        if(l==r){
            tree[i] = A[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            tree[i] = v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    int query(int i, int l, int r, ll v){
        if(l==r) return l;
        int m = (l+r)>>1;
        if(tree[i*2+1] >= v) return query(i*2+1, m+1, r, v);
        else return query(i*2, l, m, v-tree[i*2+1]);
    }
} sumTree;

struct segTree{
    ll val[1<<20], sum[1<<20], minPrf[1<<20];

    void init(int i, int l, int r, ll *delta){
        if(l==r){
            val[i] = delta[l];
            sum[i] = minPrf[i] = val[i];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, delta);
        init(i*2+1, m+1, r, delta);

        sum[i] = sum[i*2] + sum[i*2+1];
        minPrf[i] = min(minPrf[i*2], sum[i*2] + minPrf[i*2+1]);
    }

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            val[i] = v;
            sum[i] = minPrf[i] = val[i];
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        sum[i] = sum[i*2] + sum[i*2+1];
        minPrf[i] = min(minPrf[i*2], sum[i*2] + minPrf[i*2+1]);
    }

    pair<ll, ll> prefixQuery(int i, int l, int r, int s, int e){
        if(r<s || e<l) return make_pair(0LL, 0LL);
        if(s<=l && r<=e) return make_pair(sum[i], minPrf[i]);
        int m = (l+r)>>1;
        pair<ll, ll> a = prefixQuery(i*2, l, m, s, e), b = prefixQuery(i*2+1, m+1, r, s, e);
        return make_pair(a.first + b.first, min(a.second, a.first + b.second));
    }
} tree;

int n, q;
ll arr[500002];
ll half[500002];
ll val[500002];
ll delta[500002];

set<int> odd, even;
ll ans;

void recal(int x){
    if(x<1 || x>n) return;
    delta[x] = arr[x*2-2]+arr[x*2-1]-(half[x*2-2]+half[x*2-1])*2-half[x];
    tree.update(1, 1, n, x, delta[x]);
}

void changeValue(int x, ll v){
    fenwick.add(x, v);
    halfFenwick.add(x, (arr[x]+v) / 2 - half[x]);
    arr[x] += v;
    half[x] = arr[x] / 2;
    sumTree.update(1, 1, n, x, half[x]);

//    for(int i=1; i<=n; i++) recal(i);
    recal(x), recal(x/2), recal(x/2+1);
}

bool able(ll v){
    if(halfFenwick.sum(1, n) < v) return false;
    int x = sumTree.query(1, 1, n, v);
    ll xp = v - halfFenwick.sum(x+1, n);

    /// 먼저 x에서 xp 체크
    ll s = 0;
    if(x){
        ll tmpHalf = halfFenwick.sum(x, x);
        halfFenwick.add(x, xp - tmpHalf);
        s = fenwick.sum(x+x-1) - halfFenwick.sum(x, x+x-1)*2 - halfFenwick.sum(x, x);
        halfFenwick.add(x, tmpHalf - xp);
    }
    if(s<0) return false;

    return s + tree.prefixQuery(1, 1, n, x+1, n).second >= 0;
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]), half[i] = arr[i]/2;

    fenwick.init(n);
    halfFenwick.init(n);
    sumTree.init(1, 1, n, half);
    for(int i=1; i<=n; i++){
        fenwick.add(i, arr[i]), halfFenwick.add(i, half[i]);
    }
    for(int i=1; i<=n; i++){
        delta[i] = arr[i*2-2]+arr[i*2-1]-(half[i*2-2]+half[i*2-1])*2-half[i];
    }

    tree.init(1, 1, n, delta);

    while(q--){
        int x; ll v;
        scanf("%d %lld", &x, &v);
        changeValue(x, v);

        ll L = 0, R = 1e16, ANS=0;
        while(L<=R){
            ll MID = (L+R)/2;
            if(able(MID)) ANS = MID, L=MID+1;
            else R = MID-1;
        }
        printf("%lld\n", ANS);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:158:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]), half[i] = arr[i]/2;
      |                             ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         scanf("%d %lld", &x, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5