Submission #1031720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031720		vjudge1	Sequence (APIO23_sequence)	C++17	0 / 100	639 ms	78932 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
struct segtree{
    struct info{
        int mxprf;
        int mnprf;
        int mxsuf;
        int mnsuf;
        int sum;
        info(){
            mxprf=mnprf=mxsuf=mnsuf=0;
        }
        info(int k){
            mxprf=mnprf=mxsuf=mnsuf=0;
            if(k>0)mxprf=mxsuf=sum=0;
            else mnprf=mnsuf=sum=k;
        }
        info(info a,info b){
            sum=a.sum+b.sum;
            mxprf=max(a.mxprf,b.mxprf+a.sum);
            mnprf=min(a.mnprf,b.mnprf+a.sum);
            mxsuf=max(b.mxsuf,a.mxsuf+b.sum);
            mnsuf=min(b.mnsuf,a.mnsuf+b.sum);
        }
    } T[1<<20];
    void upd(int i,int l,int r,int p,int x){
        if(l==r)return void(T[i]=info(x));
        if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
        else upd(i*2,l,l+r>>1,p,x);
        T[i]=info(T[i*2],T[i*2+1]);
    }
    info qry(int i,int l,int r,int ll,int rr){
        if(ll>r||l>rr)return info();
        if(ll<=l&&r<=rr) return T[i];
        return info(qry(i*2,l,l+r>>1,ll,rr),
                qry(i*2+1,l+r+2>>1,r,ll,rr));
    }
} TRE;
    int CC=0;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>stt;
map<int,int>mp;
vector<int>pos[500100];
int sequence(int N, std::vector<int> A) {
    int ans=1;

    for(auto i:A)mp[i];
    for(auto&[i,j]:mp)
        j=++CC;
    for(auto&i:A)
        i=mp[i];
    for(int i=0;i<N;i++)
        pos[A[i]].push_back(i+1);
    for(int i=1;i<=N;i++)
        TRE.upd(1,1,N,i,1);
    for(int i=1;i<=CC;i++){
        for(auto k:pos[i])
            TRE.upd(1,1,N,k,0);
        if(pos[i].size()==2){
            int x=TRE.qry(1,1,N,pos[i][0],pos[i][1]).sum;
            if(x>0){
                x+=TRE.qry(1,1,N,1,pos[i][0]-1).mnsuf;
                x+=TRE.qry(1,1,N,pos[i][1]+1,N).mnprf;
                if(x<3) return 2;
            } else {
                x+=TRE.qry(1,1,N,1,pos[i][0]-1).mxsuf;
                x+=TRE.qry(1,1,N,pos[i][1]+1,N).mxprf;
                if(x>-3) return 2;
            }
        }
        for(auto k:pos[i])
            TRE.upd(1,1,N,k,-1);
    }
    return 1;
}

Compilation message (stderr)

sequence.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
sequence.cpp:31:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
      |            ~^~
sequence.cpp:31:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
      |                                ~~~^~
sequence.cpp:32:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         else upd(i*2,l,l+r>>1,p,x);
      |                        ~^~
sequence.cpp: In member function 'segtree::info segtree::qry(int, int, int, int, int)':
sequence.cpp:38:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         return info(qry(i*2,l,l+r>>1,ll,rr),
      |                               ~^~
sequence.cpp:39:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |                 qry(i*2+1,l+r+2>>1,r,ll,rr));
      |                           ~~~^~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:48:9: warning: unused variable 'ans' [-Wunused-variable]
   48 |     int ans=1;
      |         ^~~

• 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