oj.uz

Submission #932104

# Submission time Handle Problem Language Result Execution time Memory
932104 2024-02-23T02:33:05 Z Edu175 Sequence (APIO23_sequence) C++17
11 / 100
 2000 ms 842092 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;
#pragma GCC optimize("Ofast") // may lead to precision errors

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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 36 ms 55132 KB Output is correct
2 Correct 30 ms 55128 KB Output is correct
3 Correct 45 ms 55128 KB Output is correct
4 Correct 361 ms 55384 KB Output is correct
5 Correct 62 ms 55364 KB Output is correct
6 Correct 41 ms 55384 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 550 ms 55632 KB Output is correct
9 Correct 326 ms 55368 KB Output is correct
10 Correct 314 ms 55388 KB Output is correct
11 Correct 306 ms 55384 KB Output is correct
12 Correct 305 ms 55384 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55132 KB Output is correct
2 Correct 30 ms 55128 KB Output is correct
3 Correct 45 ms 55128 KB Output is correct
4 Correct 361 ms 55384 KB Output is correct
5 Correct 62 ms 55364 KB Output is correct
6 Correct 41 ms 55384 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 550 ms 55632 KB Output is correct
9 Correct 326 ms 55368 KB Output is correct
10 Correct 314 ms 55388 KB Output is correct
11 Correct 306 ms 55384 KB Output is correct
12 Correct 305 ms 55384 KB Output is correct
13 Execution timed out 2051 ms 58596 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55132 KB Output is correct
2 Execution timed out 2069 ms 806792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 55128 KB Output is correct
2 Execution timed out 2058 ms 551240 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 2079 ms 842092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55132 KB Output is correct
2 Correct 30 ms 55128 KB Output is correct
3 Correct 45 ms 55128 KB Output is correct
4 Correct 361 ms 55384 KB Output is correct
5 Correct 62 ms 55364 KB Output is correct
6 Correct 41 ms 55384 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 550 ms 55632 KB Output is correct
9 Correct 326 ms 55368 KB Output is correct
10 Correct 314 ms 55388 KB Output is correct
11 Correct 306 ms 55384 KB Output is correct
12 Correct 305 ms 55384 KB Output is correct
13 Execution timed out 2051 ms 58596 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55132 KB Output is correct
2 Correct 30 ms 55128 KB Output is correct
3 Correct 45 ms 55128 KB Output is correct
4 Correct 361 ms 55384 KB Output is correct
5 Correct 62 ms 55364 KB Output is correct
6 Correct 41 ms 55384 KB Output is correct
7 Correct 19 ms 55388 KB Output is correct
8 Correct 550 ms 55632 KB Output is correct
9 Correct 326 ms 55368 KB Output is correct
10 Correct 314 ms 55388 KB Output is correct
11 Correct 306 ms 55384 KB Output is correct
12 Correct 305 ms 55384 KB Output is correct
13 Execution timed out 2051 ms 58596 KB Time limit exceeded
14 Halted 0 ms 0 KB -