oj.uz

Submission #402445

# Submission time Handle Problem Language Result Execution time Memory
402445 2021-05-11T17:14:44 Z NintsiChkhaidze Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 108188 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (node<<1),l,(l+r)>>1
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
ll sgt[4*N][5][5],a[N],b[N];
void build(int node,int l,int r){
    if (l == r){
        sgt[node][1][1] = abs(b[l]);
        sgt[node][1][0] = sgt[node][0][1]= sgt[node][0][0] = 0;
        sgt[node][2][0] = sgt[node][0][2] = b[l];
        return;
    }
    build(left),build(right);
    ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];

    //1 1
    ll p = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][1];
    ll q = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][1];
    ll z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][1];
    ll d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][1];
    
    if(x*y < 0) d=0;
    sgt[node][1][1] = max(max(p,q),max(z,d));
    
    //1 0
    p = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][0];
    q = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][0];
    z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][0];
    d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][0];
    
    if(x*y < 0) d=0;
    sgt[node][1][0] = max(max(p,q),max(z,d));
    
    //0 1
    p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][1];
    q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][1];
    z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][1];
    d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][1];
    
    if(x*y < 0) d=0;
    sgt[node][0][1] = max(max(p,q),max(z,d));
    
    //0 0
    p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][0];
    q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][0];
    z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][0];
    d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][0];
    
    if(x*y < 0) d=0;
    sgt[node][0][0] = max(max(p,q),max(z,d));
    
    sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
    sgt[node][2][0] = sgt[(node<<1)][2][0];
}
main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,q;
    cin>>n>>q;
    
    for (int i=1;i<=n;i++)
        cin>>a[i];
    
    for (int i=1;i<n;i++)
        b[i] = a[i]-a[i+1];
       
    build(1,1,n-1);
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        //if (l > 1) upd(1,1,n-1,l-1,-k);
        //if (r < n) upd(1,1,n-1,r,k);
        if (l > 1) b[l-1]-=k;
        if (r < n) b[r]+=k;
        
        build(1,1,n-1);
        ll x = max(max(sgt[1][1][1],sgt[1][0][0]),max(sgt[1][1][0],sgt[1][0][1]));
        cout<<x<<"\n";
    }
}

Compilation message

Main.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main (){
      | ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 270 ms 2084 KB Output is correct
8 Correct 266 ms 2088 KB Output is correct
9 Correct 308 ms 2068 KB Output is correct
10 Correct 291 ms 2116 KB Output is correct
11 Correct 268 ms 2080 KB Output is correct
12 Correct 226 ms 1996 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 270 ms 2084 KB Output is correct
8 Correct 266 ms 2088 KB Output is correct
9 Correct 308 ms 2068 KB Output is correct
10 Correct 291 ms 2116 KB Output is correct
11 Correct 268 ms 2080 KB Output is correct
12 Correct 226 ms 1996 KB Output is correct
13 Execution timed out 2093 ms 108188 KB Time limit exceeded
14 Halted 0 ms 0 KB -