Submission #1191803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191803		KhoaDuy	Sequence (APIO23_sequence)	C++20	0 / 100	188 ms	52036 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
struct T{
    int Minpre=0,Maxpre=0,Minsuf=0,Maxsuf=0,sum=0;
};
T TT(T &le,T &ri){
    T pa;
    pa.sum=le.sum+ri.sum;
    pa.Minpre=min(le.Minpre,le.sum+ri.Minpre);
    pa.Maxpre=max(le.Maxpre,le.sum+ri.Maxpre);
    pa.Minsuf=min(ri.Minsuf,le.Minsuf+ri.sum);
    pa.Maxsuf=max(ri.Maxsuf,le.Maxsuf+ri.sum);
    return pa;
}
T Tid;
struct segtree{
    vector<T> seg;
    int n,lg;
    void refresh(int v){
        seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
    }
    void build(int siz){
        n=1;
        while(n<siz){
            n<<=1;
        }
        lg=__lg(n);
        seg.assign(n<<1,Tid);
    }
    void update(int l,int x){
        l+=n;
        seg[l].sum=x;
        seg[l].Minpre=min(0,x),seg[l].Maxpre=max(0,x);
        seg[l].Minsuf=seg[l].Minpre,seg[l].Maxsuf=seg[l].Maxpre;
        for(int i=1;i<=lg;i++){
            refresh(l>>i);
        }
    }
    T query(int l,int r){
        T le=Tid,ri=Tid;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                le=TT(le,seg[l]);
                l++;
            }
            if(r&1){
                r--;
                ri=TT(seg[r],ri);
            }
        }
        return TT(le,ri);
    }
};
struct fenwick{
    vector<int> bit;
    void build(int siz){
        bit.resize(siz+1);
        for(int i=1;i<=siz;i++){
            bit[i]=1e9;
        }
    }
    void update(int i,int x){
        for(;i<bit.size();i+=(i&(-i))){
            bit[i]=min(bit[i],x);
        }
    }
    int query(int i){
        int curr=1e9;
        for(;i;i-=(i&(-i))){
            curr=min(curr,bit[i]);
        }
        return curr;
    }
};
int sequence(int n,vector<int> a){
    segtree seg;
    vector<vector<int>> occu(n+1);
    for(int i=0;i<n;i++){
        occu[a[i]].push_back(i);
    }
    seg.build(n);
    for(int i=0;i<n;i++){
        if(a[i]>1){
            seg.update(i,-1);
        }
    }
    for(int x=1;x<=n;x++){

    }
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:91:1: warning: no return statement in function returning non-void [-Wreturn-type]
   91 | }
      | ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18