oj.uz

Submission #891031

# Submission time Handle Problem Language Result Execution time Memory
891031 2023-12-22T06:36:53 Z manizare Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 573 ms 38288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+ 10, K = 101, N = 1e6, inf = 1e18 + 1 , sq =280 , lg = 18, mod = 1e9+7 ;
int a[maxn] , val[maxn] ,n , q; 

struct node{
    int a[2][2] , f, e ; 
};
node seg[4*maxn] ;
node operator+(node a , node b){
    node res ;
    res.f=  a.f;
    res.e=  b.e; 
    rep(i , 0 , 1){
        rep(j , 0 , 1){
            res.a[i][j] = -inf ; 
            rep(k , 0 , 1){
                rep(f ,0 , 1){
                    if(a.e*b.f < 0 && f==1 && k == 1){
                        continue ;
                    }
                    res.a[i][j] = max(res.a[i][j] , a.a[i][k] + b.a[f][j]) ; 
                }
            }
        }
    }
    return res; 
}

void UPD(int x , int w , int p = 1, int l = 1, int r = n-1){
    int mid = (l+r)/2 , pl = p << 1 ,pr = p<<1 | 1 ;
    if(x > r || x < l)return ;
    if(x==l && x== r){
        rep(i,0,1)rep(j ,0 ,1)if(i+j != 2)seg[p].a[i][j] = -inf ;
        seg[p].f += w; 
        seg[p].e += w; 
        seg[p].a[1][1] = abs(seg[p].e) ;
        seg[p].a[0][0] = 0; 
        return ; 
    }
    UPD(x,w,pl,l,mid);
    UPD(x,w,pr,mid+1,r);
    seg[p] = seg[pl] + seg[pr] ;
}

void upd(int v, int w){
    val[v] +=w ; 
    UPD(v,w);
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> q ;
    rep(i , 1, n){
        cin >> a[i] ;
        if(i!=1)upd(i-1 , -a[i]) ;
        if(i!=n)upd(i , a[i]) ;
    }
    while(q--){
        int l  , r , w ;
        cin >> l >> r >> w ;
        if(l!=1){
            upd(l-1, -w) ;
        }
        if(r!=n){
            upd(r , w) ;
        }
        int ans =0 ;
        rep(i , 0 , 1)rep(j , 0 , 1)ans = max(ans , seg[1].a[i][j]) ;
        cout << ans << "\n" ;
    }
}   
/*


*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 7 ms 2908 KB Output is correct
8 Correct 5 ms 2904 KB Output is correct
9 Correct 5 ms 2908 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 5 ms 2724 KB Output is correct
12 Correct 5 ms 2904 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 7 ms 2908 KB Output is correct
8 Correct 5 ms 2904 KB Output is correct
9 Correct 5 ms 2908 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 5 ms 2724 KB Output is correct
12 Correct 5 ms 2904 KB Output is correct
13 Correct 547 ms 36484 KB Output is correct
14 Correct 530 ms 37624 KB Output is correct
15 Correct 521 ms 37592 KB Output is correct
16 Correct 522 ms 37708 KB Output is correct
17 Correct 573 ms 37624 KB Output is correct
18 Correct 461 ms 38288 KB Output is correct