oj.uz

Submission #901601

# Submission time Handle Problem Language Result Execution time Memory
901601 2024-01-09T16:30:31 Z imarn Progression (NOI20_progression) C++14
35 / 100
 264 ms 78672 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
struct node{
    ll al,ar,mxl,mxr,mx,sz,dl,dr;
    node operator+(node b){
        node tmp;tmp.al=al;tmp.ar=b.ar;tmp.sz=sz+b.sz;
        tmp.mxl=max(mxl,1ll*2);tmp.mx=max({mx,b.mx,1ll*2});
        tmp.mxr=max(b.mxr,1ll*2);
        if(sz==0&&b.sz==0)return {0,0,0,0,0,0,0};
        else if(sz==0)return b;
        else if(b.sz==0)return {al,ar,mxl,mxr,mx,sz,dl,dr};
        else if(sz==1&&b.sz==1){
            tmp.mxl=2;tmp.mxr=2;tmp.mx=2;
            tmp.dl=b.al-ar,tmp.dr=b.al-ar;
        }
        else if(sz==1){
            if(b.al-ar==b.dl)tmp.mxl = max(tmp.mxl,1+b.mxl);
            if(b.al-ar==b.dl&&b.mxr==b.sz)tmp.mxr=max(tmp.mxr,1+b.mxr);
            if(b.al-ar==b.dl)tmp.mx=max(tmp.mx,1+b.mxl);
            tmp.dr=b.dr;tmp.dl=b.al-ar;
        }
        else if(b.sz==1){
            if(b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+1});
            if(b.al-ar==dr)tmp.mxr=max(tmp.mxr,1+mxr);
            if(b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+1);
            tmp.dr=b.al-ar;tmp.dl=dl;
        }
        else {
            if(dr==b.dl&&b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+b.mxl});
            if(dr==b.dl&&b.al-ar==dr&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,mxr+b.mxr});
            if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
            if(b.al-ar==dr&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+1});
            if(b.al-ar==b.dl&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,b.mxr+1});
            if(b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+1);
            if(b.al-ar==b.dl)tmp.mx=max(tmp.mx,b.mxl+1);
        }return tmp;
    }
}t[4*N];
ll a[N];
void build(int i,int l,int r){
    if(l==r)return void(t[i]={a[l],a[l],1,1,1,1,0,0});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
node qr(int i,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return {0,0,0,0,0,0,0,0};
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--){
        int x,l,r;cin>>x>>l>>r;
        cout<<qr(1,1,n,l,r).mx<<'\n';
    }
}

Compilation message

Progression.cpp: In member function 'node node::operator+(node)':
Progression.cpp:38:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |             if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
      |             ^~
Progression.cpp:38:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |             if(dr==b.dl&&b.al-ar==dr)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
      |                                                                   ^~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 71328 KB Output is correct
2 Correct 73 ms 2912 KB Output is correct
3 Correct 78 ms 3156 KB Output is correct
4 Correct 73 ms 3080 KB Output is correct
5 Correct 74 ms 3152 KB Output is correct
6 Correct 74 ms 3156 KB Output is correct
7 Correct 75 ms 5200 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 254 ms 75884 KB Output is correct
12 Correct 227 ms 77416 KB Output is correct
13 Correct 250 ms 75860 KB Output is correct
14 Correct 259 ms 75860 KB Output is correct
15 Correct 223 ms 77392 KB Output is correct
16 Correct 264 ms 77932 KB Output is correct
17 Correct 260 ms 78028 KB Output is correct
18 Correct 255 ms 77904 KB Output is correct
19 Correct 236 ms 77396 KB Output is correct
20 Correct 240 ms 77216 KB Output is correct
21 Correct 227 ms 77300 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 71328 KB Output is correct
2 Correct 73 ms 2912 KB Output is correct
3 Correct 78 ms 3156 KB Output is correct
4 Correct 73 ms 3080 KB Output is correct
5 Correct 74 ms 3152 KB Output is correct
6 Correct 74 ms 3156 KB Output is correct
7 Correct 75 ms 5200 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 254 ms 75884 KB Output is correct
12 Correct 227 ms 77416 KB Output is correct
13 Correct 250 ms 75860 KB Output is correct
14 Correct 259 ms 75860 KB Output is correct
15 Correct 223 ms 77392 KB Output is correct
16 Correct 264 ms 77932 KB Output is correct
17 Correct 260 ms 78028 KB Output is correct
18 Correct 255 ms 77904 KB Output is correct
19 Correct 236 ms 77396 KB Output is correct
20 Correct 240 ms 77216 KB Output is correct
21 Correct 227 ms 77300 KB Output is correct
22 Incorrect 237 ms 78672 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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