Submission #954526

#	Time	Username	Problem	Language	Result	Execution time	Memory
954526		Trisanu_Das	Sequence (APIO23_sequence)	C++17	100 / 100	779 ms	69704 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>
#define re register
using namespace std;
int n,m,a[500002],ans,mx[2000002],mn[2000002],sum,tg[2000002],Mx,Mn,pmx[2000002],pmn[2000002],smx[2000002],smn[2000002],Q[500002],hd,tl;
vector<int>AA[500002];
inline void Add(re int p,re int x){
	mx[p]+=x,mn[p]+=x,tg[p]+=x;
}
inline void pd(re int p){
	if(tg[p])Add(p<<1,tg[p]),Add(p<<1|1,tg[p]),tg[p]=0;
}
inline void pu(re int p){
	mx[p]=max(mx[p<<1],mx[p<<1|1]);
	mn[p]=min(mn[p<<1],mn[p<<1|1]);
}
inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
	if(l>=x&&r<=y)return Add(p,z);
	pd(p);
	re int mid=l+r>>1;
	if(x<=mid)add(p<<1,l,mid,x,y,z);
	if(y>mid)add(p<<1|1,mid+1,r,x,y,z);
	pu(p);
}
inline void ask(re int p,re int l,re int r,re int x,re int y){
	if(l>=x&&r<=y){
		Mx=max(Mx,mx[p]),Mn=min(Mn,mn[p]);
		return;
	}
	pd(p);
	re int mid=l+r>>1;
	if(x<=mid)ask(p<<1,l,mid,x,y);
	if(y>mid)ask(p<<1|1,mid+1,r,x,y);
}
int sequence(int N, std::vector<int> A){
	n=N;
	for(re int i=1;i<=n;++i)a[i]=A[i-1],AA[a[i]].push_back(i),add(1,0,n,i,n,1);
	for(re int i=1;i<=n;++i){
		for(auto z:AA[i])Mn=1e9,ask(1,0,n,0,z-1),pmn[z]=Mn,Mx=-1e9,ask(1,0,n,z,n),smx[z]=Mx;
		for(auto z:AA[i])add(1,0,n,z,n,-2);
		for(auto z:AA[i])Mx=-1e9,ask(1,0,n,0,z-1),pmx[z]=Mx,Mn=1e9,ask(1,0,n,z,n),smn[z]=Mn;
		hd=1,tl=0;
		for(auto z:AA[i]){
			Q[++tl]=z;
			while(hd<=tl&&1ll*(smx[z]-pmn[Q[hd]])*(smn[z]-pmx[Q[hd]])>0)++hd;
			ans=max(ans,tl-hd+1);
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp:7:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 | inline void Add(re int p,re int x){
      |                        ^
sequence.cpp:7:33: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 | inline void Add(re int p,re int x){
      |                                 ^
sequence.cpp:10:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   10 | inline void pd(re int p){
      |                       ^
sequence.cpp:13:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   13 | inline void pu(re int p){
      |                       ^
sequence.cpp:17:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 | inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
      |                        ^
sequence.cpp:17:33: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 | inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
      |                                 ^
sequence.cpp:17:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 | inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
      |                                          ^
sequence.cpp:17:51: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 | inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
      |                                                   ^
sequence.cpp:17:60: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 | inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
      |                                                            ^
sequence.cpp:17:69: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 | inline void add(re int p,re int l,re int r,re int x,re int y,re int z){
      |                                                                     ^
sequence.cpp: In function 'void add(int, int, int, int, int, int)':
sequence.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  re int mid=l+r>>1;
      |             ~^~
sequence.cpp:20:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   20 |  re int mid=l+r>>1;
      |         ^~~
sequence.cpp: At global scope:
sequence.cpp:25:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 | inline void ask(re int p,re int l,re int r,re int x,re int y){
      |                        ^
sequence.cpp:25:33: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 | inline void ask(re int p,re int l,re int r,re int x,re int y){
      |                                 ^
sequence.cpp:25:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 | inline void ask(re int p,re int l,re int r,re int x,re int y){
      |                                          ^
sequence.cpp:25:51: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 | inline void ask(re int p,re int l,re int r,re int x,re int y){
      |                                                   ^
sequence.cpp:25:60: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 | inline void ask(re int p,re int l,re int r,re int x,re int y){
      |                                                            ^
sequence.cpp: In function 'void ask(int, int, int, int, int)':
sequence.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  re int mid=l+r>>1;
      |             ~^~
sequence.cpp:31:9: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |  re int mid=l+r>>1;
      |         ^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:37:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 |  for(re int i=1;i<=n;++i)a[i]=A[i-1],AA[a[i]].push_back(i),add(1,0,n,i,n,1);
      |             ^
sequence.cpp:38:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   38 |  for(re int i=1;i<=n;++i){
      |             ^

• 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