oj.uz

Submission #932102

# Submission time Handle Problem Language Result Execution time Memory
932102 2024-02-23T02:30:46 Z Edu175 Sequence (APIO23_sequence) C++17
11 / 100
 2000 ms 801124 KB 
#include "sequence.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,apio=b;i<apio;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto slkdh:v)cout<<slkdh<<" ";cout<<"\n"
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
const ll C=5e5,MAXN=2*C+5;

unordered_map<ll,ll> ft[MAXN+1];
void upd(ll p, ll q, ll v){
	p+=C,q+=C;
	p=MAXN-1-p; v-=C;
	//cout<<"upd "<<p<<","<<q<<" "<<-v<<"\n";
	for(ll i=p+1;i<=MAXN;i+=i&-i)
	for(ll j=q+1;j<=MAXN;j+=j&-j){
		ll &r=ft[i][j];
		r=min(r,v);
	}
}
ll query(ll p, ll q){
	p+=C,q+=C;
	p=MAXN-1-p;
	//cout<<"query "<<p<<","<<q<<"\n";
	ll res=0;
	for(ll i=p+1;i;i-=i&-i)
	for(ll j=q+1;j;j-=j&-j){
		res=min(res,ft[i][j]);
	}
	//cout<<res<<" res\n";
	return res+C;
}

int sequence(int N, std::vector<int> A) {
	ll n=N;
	vector<ll>a(n);
	fore(i,0,n)a[i]=A[i]-1;
	vector<ll>pos[n];
	fore(i,0,n)pos[a[i]].pb(i);
	vector<ll>s(n);
	fore(i,0,n)s[i]=1;
	ll res=0;
	fore(i,0,n)if(SZ(pos[i])){
		//cout<<"\nin"<<i<<":\n";
		for(auto j:pos[i])s[j]=0;
		//imp(s);
		fore(j,0,MAXN)ft[j].clear();
		upd(0,0,0);
		ll sum=0,rew=0;
		fore(j,0,n){
			sum+=s[j],rew+=a[j]==i;
			ll p=sum-rew,q=sum+rew;
			res=max(res,rew-query(p,q));
			upd(p,q,rew);
			//cout<<j<<": "<<sum<<" "<<rew<<"\n";
			//cout<<"add "<<p<<","<<q<<" "<<rew<<"\n";
			//cout<<res<<"\n\n";
		}
		//cout<<res<<"\n";
		for(auto j:pos[i])s[j]=-1;
	}
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55128 KB Output is correct
2 Correct 29 ms 55740 KB Output is correct
3 Correct 44 ms 55132 KB Output is correct
4 Correct 352 ms 55396 KB Output is correct
5 Correct 72 ms 55376 KB Output is correct
6 Correct 40 ms 55232 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 535 ms 55632 KB Output is correct
9 Correct 286 ms 55384 KB Output is correct
10 Correct 325 ms 55376 KB Output is correct
11 Correct 296 ms 55368 KB Output is correct
12 Correct 304 ms 55632 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55128 KB Output is correct
2 Correct 29 ms 55740 KB Output is correct
3 Correct 44 ms 55132 KB Output is correct
4 Correct 352 ms 55396 KB Output is correct
5 Correct 72 ms 55376 KB Output is correct
6 Correct 40 ms 55232 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 535 ms 55632 KB Output is correct
9 Correct 286 ms 55384 KB Output is correct
10 Correct 325 ms 55376 KB Output is correct
11 Correct 296 ms 55368 KB Output is correct
12 Correct 304 ms 55632 KB Output is correct
13 Execution timed out 2033 ms 58572 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55128 KB Output is correct
2 Execution timed out 2077 ms 785968 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 55740 KB Output is correct
2 Execution timed out 2068 ms 551144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 801124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55128 KB Output is correct
2 Correct 29 ms 55740 KB Output is correct
3 Correct 44 ms 55132 KB Output is correct
4 Correct 352 ms 55396 KB Output is correct
5 Correct 72 ms 55376 KB Output is correct
6 Correct 40 ms 55232 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 535 ms 55632 KB Output is correct
9 Correct 286 ms 55384 KB Output is correct
10 Correct 325 ms 55376 KB Output is correct
11 Correct 296 ms 55368 KB Output is correct
12 Correct 304 ms 55632 KB Output is correct
13 Execution timed out 2033 ms 58572 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 55128 KB Output is correct
2 Correct 29 ms 55740 KB Output is correct
3 Correct 44 ms 55132 KB Output is correct
4 Correct 352 ms 55396 KB Output is correct
5 Correct 72 ms 55376 KB Output is correct
6 Correct 40 ms 55232 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 535 ms 55632 KB Output is correct
9 Correct 286 ms 55384 KB Output is correct
10 Correct 325 ms 55376 KB Output is correct
11 Correct 296 ms 55368 KB Output is correct
12 Correct 304 ms 55632 KB Output is correct
13 Execution timed out 2033 ms 58572 KB Time limit exceeded
14 Halted 0 ms 0 KB -