oj.uz

Submission #936652

# Submission time Handle Problem Language Result Execution time Memory
936652 2024-03-02T12:43:15 Z JuanJL Sequence (APIO23_sequence) C++17
28 / 100
 605 ms 93504 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

ll n; 
vector<ll> a;


int sequence(int N, std::vector<int> A) {
	n=N;
	a.clear();
	a.resize(n);
	forn(i,0,n) a[i]=A[i];
	ll res = 0;
	
	if(n<=2*pow(10,3)){
		//Subtasks 1 , 2
		forn(i,0,n){
			indexed_multiset im;
			ll ocurr[n+1];
			mset(ocurr,0);
			forn(j,i,n){
				im.insert(a[j]);
				ocurr[a[j]]++;
				res = max(res,ocurr[*im.find_by_order((SZ(im)-1)/2)]);
				if(SZ(im)%2==0) res = max(res,ocurr[*im.find_by_order((SZ(im)-1)/2+1)]);
			}
		}
	}else{
		vector<vector<ll>> p;
		set<ll> vals;
		map<ll,ll> cI;
		forn(i,0,n) vals.insert(a[i]);
		ll ind = 0;
		for(auto i:vals) cI[i]=ind,ind++;
		p.resize(SZ(cI));
		forn(i,0,n)	p[cI[a[i]]].pb(i);
		/*forn(i,0,n){
			ll igu = SZ(p[cI[a[i]]]);
			ll men = p[cI[a[i]]][0]+(n-1)-p[cI[a[i]]][igu-1];
			ll may = (p[cI[a[i]]][igu-1]-p[cI[a[i]]][0])-igu;
			if(may<=men+igu){
				res=max(res,igu);
			}else{
				ll preRes = 0;
				forn(j,0,SZ(p[cI[a[i]]])){
					if(abs(p[cI[a[i]]][j]-p[cI[a[i]]][j-1])==1) preRes++;
					else break;
				}
				res=max(res,max(preRes,SZ(p[cI[a[i]]])-preRes));
			} 
		}*/
		ll men = 0;
		ll may = 0;
		ll igu = 0;
		forn(i,0,SZ(p)){
			men=0; may = 0; igu = 0;
			forn(j,0,SZ(p[i])){
				if(abs(p[i][j]-p[i][j-1])==1) igu++;
				else break;
			}
			res=max(res,igu);
			res=max(res,SZ(p[i])-(igu+1));
			may=(p[i][igu+1]-p[i][igu])-1;
			if(may<=men+igu) res = max(res,(ll)SZ(p[i]));
		}
	}
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 365 ms 544 KB Output is correct
14 Correct 361 ms 344 KB Output is correct
15 Correct 354 ms 544 KB Output is correct
16 Correct 348 ms 344 KB Output is correct
17 Correct 333 ms 548 KB Output is correct
18 Correct 312 ms 548 KB Output is correct
19 Correct 368 ms 544 KB Output is correct
20 Correct 364 ms 544 KB Output is correct
21 Correct 376 ms 548 KB Output is correct
22 Correct 383 ms 348 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 282 ms 60932 KB Output is correct
3 Correct 318 ms 60748 KB Output is correct
4 Correct 46 ms 12232 KB Output is correct
5 Correct 236 ms 55872 KB Output is correct
6 Correct 231 ms 59208 KB Output is correct
7 Incorrect 48 ms 14280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 69 ms 16120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 90204 KB Output is correct
2 Correct 605 ms 93504 KB Output is correct
3 Correct 572 ms 90708 KB Output is correct
4 Correct 604 ms 90516 KB Output is correct
5 Correct 423 ms 72888 KB Output is correct
6 Incorrect 379 ms 73024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 365 ms 544 KB Output is correct
14 Correct 361 ms 344 KB Output is correct
15 Correct 354 ms 544 KB Output is correct
16 Correct 348 ms 344 KB Output is correct
17 Correct 333 ms 548 KB Output is correct
18 Correct 312 ms 548 KB Output is correct
19 Correct 368 ms 544 KB Output is correct
20 Correct 364 ms 544 KB Output is correct
21 Correct 376 ms 548 KB Output is correct
22 Correct 383 ms 348 KB Output is correct
23 Incorrect 55 ms 10068 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 365 ms 544 KB Output is correct
14 Correct 361 ms 344 KB Output is correct
15 Correct 354 ms 544 KB Output is correct
16 Correct 348 ms 344 KB Output is correct
17 Correct 333 ms 548 KB Output is correct
18 Correct 312 ms 548 KB Output is correct
19 Correct 368 ms 544 KB Output is correct
20 Correct 364 ms 544 KB Output is correct
21 Correct 376 ms 548 KB Output is correct
22 Correct 383 ms 348 KB Output is correct
23 Correct 282 ms 60932 KB Output is correct
24 Correct 318 ms 60748 KB Output is correct
25 Correct 46 ms 12232 KB Output is correct
26 Correct 236 ms 55872 KB Output is correct
27 Correct 231 ms 59208 KB Output is correct
28 Incorrect 48 ms 14280 KB Output isn't correct
29 Halted 0 ms 0 KB -