Submission #859905

#	Time	Username	Problem	Language	Result	Execution time	Memory
859905		MilosMilutinovic	Sequence (APIO23_sequence)	C++17	100 / 100	964 ms	72700 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int readint(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int mn[4000005],mx[4000005],lzy[4000005],prefmn[500005],prefmx[500005],suffmn[500005],suffmx[500005];
vector<int> pos[500005];

void push(int id){
	if(lzy[id]==0) return;
	mn[id<<1]+=lzy[id];
	mx[id<<1]+=lzy[id];
	mn[id<<1|1]+=lzy[id];
	mx[id<<1|1]+=lzy[id];
	lzy[id<<1]+=lzy[id];
	lzy[id<<1|1]+=lzy[id];
	lzy[id]=0;
}

void build(int id,int l,int r){
	if(l==r){
		mn[id]=l;
		mx[id]=l;
		return;
	}
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	mn[id]=min(mn[id<<1],mn[id<<1|1]);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
}

void change(int id,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr){
		lzy[id]+=v;
		mn[id]+=v;
		mx[id]+=v;
		push(id);
		return;
	}
	push(id);
	int mid=(l+r)/2;
	if(qr<=mid) change(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) change(id<<1|1,mid+1,r,ql,qr,v);
	else change(id<<1,l,mid,ql,qr,v),change(id<<1|1,mid+1,r,ql,qr,v);
	mn[id]=min(mn[id<<1],mn[id<<1|1]);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
}

pii query(int id,int l,int r,int ql,int qr){
	if(l>r||l>qr||r<ql||ql>qr) return mp((int)1e9,(int)-1e9);
	if(ql<=l&&r<=qr) return mp(mn[id],mx[id]);
	push(id);
	int mid=(l+r)/2;
	pii L=query(id<<1,l,mid,ql,qr);
	pii R=query(id<<1|1,mid+1,r,ql,qr);
	mn[id]=min(mn[id<<1],mn[id<<1|1]);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
	return mp(min(L.fi,R.fi),max(L.se,R.se));
}

int sgn(int x){return (x==0?0:(x<0?-1:1));}

int sequence(int n,vector<int> a){
	for(int i=1;i<=n;i++) pos[a[i-1]].pb(i);
	build(1,0,n);
	int ans=1;
	for(int v=1;v<=n;v++){
		for(int i:pos[v]) prefmn[i]=query(1,0,n,0,i-1).fi,suffmx[i]=query(1,0,n,i,n).se;
		for(int i:pos[v]) change(1,0,n,i,n,-2);
		for(int i:pos[v]) prefmx[i]=query(1,0,n,0,i-1).se,suffmn[i]=query(1,0,n,i,n).fi;
		int ptr=0;
		for(int i=0;i<pos[v].size();i++){
			while(ptr+1<pos[v].size()&&sgn(suffmx[pos[v][ptr+1]]-prefmn[pos[v][i]])!=sgn(suffmn[pos[v][ptr+1]]-prefmx[pos[v][i]])) ptr++;
			ans=max(ans,ptr-i+1);
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i=0;i<pos[v].size();i++){
      |               ~^~~~~~~~~~~~~~
sequence.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    while(ptr+1<pos[v].size()&&sgn(suffmx[pos[v][ptr+1]]-prefmn[pos[v][i]])!=sgn(suffmn[pos[v][ptr+1]]-prefmx[pos[v][i]])) ptr++;
      |          ~~~~~^~~~~~~~~~~~~~

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