oj.uz

Submission #794264

# Submission time Handle Problem Language Result Execution time Memory
794264 2023-07-26T11:41:54 Z 79brue Triangle Collection (CCO23_day2problem3) C++17
0 / 25
 4 ms 676 KB 
#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){
        ll ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

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

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;

    recal(x), recal(x/2), recal(x/2+1);
}

bool able(ll v){
    if(halfFenwick.sum(1, n) < v) return false;
    int x;
    {
        int L = 1, R = n, ANS = n+1;
        while(L<=R){
            int MID = (L+R)/2;
            if(halfFenwick.sum(MID, n) <= v) ANS = MID, R = MID-1;
            else L = MID+1;
        }
        x = ANS-1;
    }
    ll xp = v - halfFenwick.sum(x+1, n);

    /// 먼저 x에서 xp 체크
    ll s = fenwick.sum(1, x*2) + fenwick.sum(1, x*2-1) - xp -
           ((x<=1 ? 0 : x==2 ? xp : half[2*x-2]) + (x==0 ? 0 : x==1 ? xp : half[2*x-1])) * 2;
    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);
    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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -