oj.uz

Submission #901595

# Submission time Handle Problem Language Result Execution time Memory
901595 2024-01-09T16:20:11 Z imarn Progression (NOI20_progression) C++14
0 / 100
 225 ms 43780 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{
    int al,ar,mxl,mxr,mx,sz,dl,dr;
    node operator+(node b){
        node tmp;tmp.al=al;tmp.ar=b.ar;
        tmp.mxl=max(mxl,2);tmp.mx=max({mx,b.mx,2});
        tmp.mxr=max(b.mxr,2);
        tmp.sz=sz+b.sz;
        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&&mxl==sz)tmp.mxl = max({tmp.mxl,mxl+b.mxl});
            if(dr==b.dl&&b.mxr==b.sz)tmp.mxr=max({tmp.mxr,mxr+b.mxr});
            if(dr==b.dl)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];
int 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:39:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |             if(dr==b.dl)tmp.mx=max(tmp.mx,mxr+b.mxl);tmp.dl=dl,tmp.dr=b.dr;
      |             ^~
Progression.cpp:39:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |             if(dr==b.dl)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 143 ms 42620 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 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 42052 KB Output is correct
2 Correct 75 ms 5200 KB Output is correct
3 Correct 82 ms 4960 KB Output is correct
4 Correct 75 ms 4932 KB Output is correct
5 Correct 79 ms 5240 KB Output is correct
6 Incorrect 77 ms 5116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 42052 KB Output is correct
2 Correct 75 ms 5200 KB Output is correct
3 Correct 82 ms 4960 KB Output is correct
4 Correct 75 ms 4932 KB Output is correct
5 Correct 79 ms 5240 KB Output is correct
6 Incorrect 77 ms 5116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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