oj.uz

Submission #891030

# Submission time Handle Problem Language Result Execution time Memory
891030 2023-12-22T06:36:20 Z manizare Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 107 ms 36136 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 = 1e5+ 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 348 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 816 KB Output is correct
8 Correct 5 ms 1020 KB Output is correct
9 Correct 5 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 1016 KB Output is correct
12 Correct 5 ms 860 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 816 KB Output is correct
8 Correct 5 ms 1020 KB Output is correct
9 Correct 5 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 1016 KB Output is correct
12 Correct 5 ms 860 KB Output is correct
13 Runtime error 107 ms 36136 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -