oj.uz

Submission #933039

# Submission time Handle Problem Language Result Execution time Memory
933039 2024-02-24T22:47:50 Z Edu175 Sequence (APIO23_sequence) C++17
63 / 100
 1916 ms 88572 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("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll INF=5e6;
struct node{
	ll mxp,mnp,mxs,mns,sum;
};
node oper(node a, node b){
	a.mxp=max(a.mxp,a.sum+b.mxp);
	a.mnp=min(a.mnp,a.sum+b.mnp);
	a.mxs=max(a.mxs+b.sum,b.mxs);
	a.mns=min(a.mns+b.sum,b.mns);
	a.sum+=b.sum;
	return a;
}
node NEUT({-INF,INF,-INF,INF,0});
struct STcustom{
	vector<node>t; ll n;
	STcustom(ll n):t(2*n+5,node({0,0,0,0,0})),n(n){}
	void upd(ll p, ll v){
		p+=n;
		t[p].mxp+=v,t[p].mnp+=v,t[p].mxs+=v,t[p].mns+=v,t[p].sum+=v;
		for(;p>1;p>>=1)p^=p&1,t[p>>1]=oper(t[p],t[p^1]);
	}
	node query(ll l, ll r){
		node izq=NEUT,der=NEUT;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1){
			if(l&1)izq=oper(izq,t[l++]);
			if(r&1)der=oper(t[--r],der);
		}
		return oper(izq,der);
	}
};
const ll C=8e4,MAXN=2*C+5;
int ft[MAXN+1]; // for more dimensions, make ft multi-dimensional
void upd(int i0, int v){ // add v to i0th element (0-based)
	// add extra fors for more dimensions
	for(int i=i0+1;i<=MAXN;i+=i&-i)ft[i]=min(ft[i],v);
}
int get(int i0){ // get sum of range [0,i0)
	int r=INF;
	// add extra fors for more dimensions
	for(int i=i0;i;i-=i&-i)r=min(r,ft[i]);
	return r;
}
ll l[MAXN],r[MAXN];
bool cmp(ll i, ll j){
	return ii({l[i],i})<ii({l[j],j});
}
const ll B=84;
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);
	STcustom st(n);
	fore(i,0,n)st.upd(i,1);
	ll res=1;
	vector<ll>s(n);
	fore(i,0,n)s[i]=1;
	fore(i,0,n)if(SZ(pos[i])){
		vector<ll>&v=pos[i];
		for(auto j:v)st.upd(j,-1),s[j]--;
		if(SZ(v)<B){
			vector<node> pre(SZ(v)),suf(SZ(v));
			fore(j,0,SZ(v)){
				ll p=v[j];
				pre[j]=st.query(0,p+1);
				suf[j]=st.query(p,n);
			}
			fore(s,0,SZ(v))fore(e,s+1,SZ(v)){
				ll dif=pre[e].sum-pre[s].sum;
				if(dif<=0){
					if(dif+pre[s].mxs+suf[e].mxp+e-s+1>=0)
						res=max(res,e-s+1);
				}
				else {
					if(dif+pre[s].mns+suf[e].mnp-(e-s+1)<=0)
						res=max(res,e-s+1);
				}
			}
		}
		else {
			ll sum=0,rew=0;
			vector<ll>rw(n+1);
			vector<ll>ev{n};
			l[n]=r[n]=rw[n]=0;
			fore(j,0,n){
				sum+=s[j],rew+=a[j]==i;
				rw[j]=rew;
				l[j]=sum-rew,r[j]=sum+rew;
				ev.pb(j);
			}
			sort(ALL(ev),cmp); reverse(ALL(ev));
			fore(i,0,MAXN)ft[i]=INF;
			for(auto i:ev){
				res=max(res,rw[i]-get(r[i]+C+1));
				upd(r[i]+C,rw[i]);
			}
		}
		for(auto j:v)st.upd(j,-1),s[j]--;
	}
	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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 1116 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 1552 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 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 264 ms 49584 KB Output is correct
3 Correct 274 ms 49508 KB Output is correct
4 Runtime error 114 ms 88128 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 135 ms 88572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 55124 KB Output is correct
2 Correct 363 ms 55216 KB Output is correct
3 Correct 353 ms 54624 KB Output is correct
4 Correct 359 ms 54608 KB Output is correct
5 Correct 292 ms 51280 KB Output is correct
6 Correct 326 ms 51280 KB Output is correct
7 Correct 254 ms 49876 KB Output is correct
8 Correct 247 ms 49744 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 1116 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 1552 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 46 ms 8284 KB Output is correct
24 Correct 46 ms 8280 KB Output is correct
25 Correct 45 ms 8284 KB Output is correct
26 Correct 1915 ms 10132 KB Output is correct
27 Correct 1898 ms 10340 KB Output is correct
28 Correct 1916 ms 10300 KB Output is correct
29 Correct 57 ms 9520 KB Output is correct
30 Correct 56 ms 9672 KB Output is correct
31 Correct 28 ms 9300 KB Output is correct
32 Correct 42 ms 9820 KB Output is correct
33 Correct 52 ms 10488 KB Output is correct
34 Correct 52 ms 10444 KB Output is correct
35 Correct 51 ms 10440 KB Output is correct
36 Correct 66 ms 10304 KB Output is correct
37 Correct 51 ms 10452 KB Output is correct
38 Correct 49 ms 10444 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 1116 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 1552 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 264 ms 49584 KB Output is correct
24 Correct 274 ms 49508 KB Output is correct
25 Runtime error 114 ms 88128 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -