Submission #749203

#	Time	Username	Problem	Language	Result	Execution time	Memory
749203		kshitij_sodani	Sequence (APIO23_sequence)	C++17	100 / 100	1585 ms	52040 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'

#include "sequence.h"

#include <vector>

vector<int> it;
int ans=0;
int tree[4*500001][2];
int lazy[4*500001];

void build(int no,int l,int r){
	lazy[no]=0;
	if(l==r){
		tree[no][0]=r+1;
		tree[no][1]=-(r+1);
	}
	if(l<r){
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
	}
}
void push(int no,int l,int r){
	tree[no][0]+=lazy[no];
	tree[no][1]-=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
}
void update(int no,int l,int r,int aa,int bb,int x){
	push(no,l,r);
	if(r<aa or l>bb or aa>bb){
		return ;
	}
	if(aa<=l and r<=bb){
		lazy[no]=x;
		push(no,l,r);
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x);
		update(no*2+2,mid+1,r,aa,bb,x);
		tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
	}
}
int query(int no,int l,int r,int aa,int bb,int x){
	push(no,l,r);
	if(r<aa or l>bb or aa>bb){
		return -1e8;
	}
	if(aa<=l and r<=bb){
		return tree[no][x];
		//return {tree[no][0],tree[no][1]};
	}
	int mid=(l+r)/2;
	return max(query(no*2+1,l,mid,aa,bb,x),query(no*2+2,mid+1,r,aa,bb,x));
/*	int mid=(l+r)/2;
	pair<int,int> x=query(no*2+1,l,mid,aa,bb);
	pair<int,int> y=query(no*2+2,mid+1,r,aa,bb);
	
	tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]);
	tree[no][1]=min(tree[no*2+1][1],tree[no*2+2][1]);
	
	return {max(x.a,y.a),min(x.b,y.b)};*/
}
int xa;
int ya;
void query4(int no,int l,int r,int i){
	if(r<=i){
		ya=max(ya,tree[no][1]);
		return;
	}
	if(l>i){
		xa=max(xa,tree[no][0]);
		return;
	}
	int mid=(l+r)/2;
	query4(no*2+1,l,mid,i);
	query4(no*2+2,mid+1,r,i);
}
int tree2[4*500001];
void update2(int no,int l,int r,int i,int x){
	if(l==r){
		tree2[no]=x;
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i,x);
		}
		else{
			update2(no*2+2,mid+1,r,i,x);
		}
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
	}
}
int query2(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return -1e8;
	}
	if(aa<=l and r<=bb){
		return tree2[no];
	}
	int mid=(l+r)/2;

	return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
int query3(int no,int l,int r,int x){
	if(l==r){
		return l;
	}
	int mid=(l+r)/2;
	if(tree2[no*2+1]>=x){
		return query3(no*2+1,l,mid,x);
	}
	return query3(no*2+2,mid+1,r,x);
}

int ind5[500001];
vector<int> pre[500001];
void solve(int n){
	for(int i=0;i<n;i++){
		pre[i].clear();
	}
	for(int i=0;i<n;i++){
		pre[it[i]].pb(i);	
	}

	build(0,0,n);
	for(int i=0;i<n;i++){
		if(pre[i].size()==1){
			for(auto j:pre[i]){
				update(0,0,n,j+1,n,-2);
			}
		}
		
		if(pre[i].size()>1){
			for(auto j:pre[i]){
				update(0,0,n,j+1,n,-1);
			}
			vector<pair<int,int>> zz;
			for(int j=0;j<pre[i].size();j++){
				ind5[pre[i][j]]=j;
				zz.pb({-query(0,0,n,pre[i][j],pre[i][j],0),j});
			}
			sort(zz.begin(),zz.end());
			int nn=zz.size();
			for(int j=0;j<4*nn;j++){
				tree2[j]=-1e8;
			}
			for(auto j:zz){
				int ha=-j.a;
				xa=-1e8;
				ya=-1e8;
				query4(0,0,n,pre[i][j.b]);
				int x=xa-ha;
				//cur=x+j.a.a+1
				llo ac=-(x+j.b+1+ha);//query(0,0,n,j.b.b,j.b.b).a);
				//find min index with sum>=ac
				llo low=0;
				if(tree2[0]>=ac){
				/*	llo low=query3(0,0,n-1,ac);
					if(low<pre[i][j.b]){
						ans=max(ans,j.b-ind5[low]+1);
					}*/
					int low=query3(0,0,nn-1,ac);
					if(low<j.b){
						ans=max(ans,j.b-low+1);
					}
				}
				int y=ha+ya;//.b;
				//update2(0,0,n-1,pre[i][j.b],y-j.b-ha);
				update2(0,0,nn-1,j.b,y-j.b-ha);
			}
			for(auto j:pre[i]){
				update(0,0,n,j+1,n,-1);
			//update2(0,0,n-1,j,-(1e8));
			}
		}
		
	}
}
int sequence(int n,vector<int> aa) {
	it=aa;
	for(int i=0;i<n;i++){
		it[i]--;
	}
	ans=1;
	solve(n);
	for(int i=0;i<n;i++){
		it[i]=n-1-it[i];
	}
	solve(n);





	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(int)':
sequence.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |    for(int j=0;j<pre[i].size();j++){
      |                ~^~~~~~~~~~~~~~
sequence.cpp:172:9: warning: unused variable 'low' [-Wunused-variable]
  172 |     llo low=0;
      |         ^~~

• 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