oj.uz

Submission #750400

# Submission time Handle Problem Language Result Execution time Memory
750400 2023-05-29T13:13:25 Z jamezzz Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 137392 KB 
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf
#define pb push_back

#define maxn 500005

struct node{
	int s,e,m,mn,mx,lz;node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,mn=0,mx=0,lz=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		mn+=lz,mx+=lz;
		if(lz&&s!=e){
			l->lz+=lz;
			r->lz+=lz;
		}
		lz=0;
	}
	void up(int x,int y,int nv){
		if(s==x&&e==y){lz+=nv;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo(),r->ppo();
		mn=min(l->mn,r->mn);
		mx=max(l->mx,r->mx);
	}
	int qmx(int x,int y){
		if(s==x&&e==y)return mx+lz;
		ppo();
		if(y<=m)return l->qmx(x,y);
		if(x>m)return r->qmx(x,y);
		return max(l->qmx(x,m),r->qmx(m+1,y));
	}
	int qmn(int x,int y){
		if(s==x&&e==y)return mn+lz;
		ppo();
		if(y<=m)return l->qmn(x,y);
		if(x>m)return r->qmn(x,y);
		return min(l->qmn(x,m),r->qmn(m+1,y));
	}
}*prt,*srt;

int pmn[maxn],pmx[maxn],smn[maxn],smx[maxn],tot[maxn][2];
vector<int> v[maxn];

//a range is valid if sum(>=x)-sum(<x)>=0 --> find min: == x value 1
//and sum(>x)-sum(<=x)<=0 --> find max: == x value -1

inline bool check(int i,int l,int r){
	return (tot[i][0]-pmn[l]-smn[r]>=0)&&(tot[i][1]-pmx[l]-smx[r]<=0);
}

int sequence(int N,vector<int> A){
	prt=new node(0,N+1);
	srt=new node(0,N+1);
	for(int i=0;i<N;++i){
		v[A[i]].pb(i+1);
		prt->up(i+1,N+1,1);
		srt->up(0,i+1,1);
	}
	for(int i=1;i<=N;++i){
		for(int x:v[i]){
			pmn[x]=prt->qmn(0,x-1);
			smn[x]=srt->qmn(x+1,N+1);
		}
		tot[i][0]=prt->qmx(N,N);
		for(int x:v[i]){
			prt->up(x,N+1,-2);
			srt->up(0,x,-2);
		}
		tot[i][1]=prt->qmx(N,N);
		for(int x:v[i]){
			pmx[x]=prt->qmx(0,x-1);
			smx[x]=srt->qmx(x+1,N+1);
		}
	}
	int ans=0;
	for(int i=1;i<=N;++i){
		if(v[i].empty())continue;
		int l=0,r=0;
		while(r<v[i].size()){
			assert(l<=r);
			if(check(i,v[i][l],v[i][r])){
				ans=max(ans,r-l+1);
				++r;
			}
			else ++l;
		}
	}
	return ans;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:87:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   while(r<v[i].size()){
      |         ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 8 ms 12060 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12016 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 8 ms 12060 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12016 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 10 ms 12500 KB Output is correct
14 Correct 10 ms 12500 KB Output is correct
15 Correct 10 ms 12528 KB Output is correct
16 Correct 10 ms 12452 KB Output is correct
17 Correct 9 ms 12500 KB Output is correct
18 Correct 10 ms 12500 KB Output is correct
19 Correct 10 ms 12472 KB Output is correct
20 Correct 10 ms 12500 KB Output is correct
21 Correct 10 ms 12500 KB Output is correct
22 Correct 10 ms 12500 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 995 ms 131500 KB Output is correct
3 Correct 1160 ms 131500 KB Output is correct
4 Correct 906 ms 123672 KB Output is correct
5 Correct 1030 ms 130520 KB Output is correct
6 Correct 984 ms 130636 KB Output is correct
7 Correct 900 ms 124204 KB Output is correct
8 Correct 892 ms 124112 KB Output is correct
9 Correct 904 ms 124776 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 979 ms 123852 KB Output is correct
3 Correct 966 ms 123792 KB Output is correct
4 Correct 981 ms 123732 KB Output is correct
5 Correct 952 ms 123888 KB Output is correct
6 Correct 924 ms 123740 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1657 ms 137392 KB Output is correct
2 Correct 1653 ms 137288 KB Output is correct
3 Correct 1667 ms 136824 KB Output is correct
4 Correct 1679 ms 136776 KB Output is correct
5 Correct 1356 ms 133372 KB Output is correct
6 Correct 1337 ms 133452 KB Output is correct
7 Correct 1041 ms 132100 KB Output is correct
8 Correct 1058 ms 131848 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 8 ms 12060 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12016 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 10 ms 12500 KB Output is correct
14 Correct 10 ms 12500 KB Output is correct
15 Correct 10 ms 12528 KB Output is correct
16 Correct 10 ms 12452 KB Output is correct
17 Correct 9 ms 12500 KB Output is correct
18 Correct 10 ms 12500 KB Output is correct
19 Correct 10 ms 12472 KB Output is correct
20 Correct 10 ms 12500 KB Output is correct
21 Correct 10 ms 12500 KB Output is correct
22 Correct 10 ms 12500 KB Output is correct
23 Correct 249 ms 31156 KB Output is correct
24 Correct 246 ms 31220 KB Output is correct
25 Correct 255 ms 31116 KB Output is correct
26 Correct 227 ms 30164 KB Output is correct
27 Correct 232 ms 30216 KB Output is correct
28 Correct 239 ms 30144 KB Output is correct
29 Correct 161 ms 29900 KB Output is correct
30 Correct 161 ms 30004 KB Output is correct
31 Correct 138 ms 30024 KB Output is correct
32 Correct 146 ms 32064 KB Output is correct
33 Correct 234 ms 30996 KB Output is correct
34 Correct 241 ms 30992 KB Output is correct
35 Correct 232 ms 31040 KB Output is correct
36 Correct 239 ms 31056 KB Output is correct
37 Correct 227 ms 30944 KB Output is correct
38 Correct 242 ms 31052 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 8 ms 12060 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12016 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 11996 KB Output is correct
13 Correct 10 ms 12500 KB Output is correct
14 Correct 10 ms 12500 KB Output is correct
15 Correct 10 ms 12528 KB Output is correct
16 Correct 10 ms 12452 KB Output is correct
17 Correct 9 ms 12500 KB Output is correct
18 Correct 10 ms 12500 KB Output is correct
19 Correct 10 ms 12472 KB Output is correct
20 Correct 10 ms 12500 KB Output is correct
21 Correct 10 ms 12500 KB Output is correct
22 Correct 10 ms 12500 KB Output is correct
23 Correct 995 ms 131500 KB Output is correct
24 Correct 1160 ms 131500 KB Output is correct
25 Correct 906 ms 123672 KB Output is correct
26 Correct 1030 ms 130520 KB Output is correct
27 Correct 984 ms 130636 KB Output is correct
28 Correct 900 ms 124204 KB Output is correct
29 Correct 892 ms 124112 KB Output is correct
30 Correct 904 ms 124776 KB Output is correct
31 Correct 979 ms 123852 KB Output is correct
32 Correct 966 ms 123792 KB Output is correct
33 Correct 981 ms 123732 KB Output is correct
34 Correct 952 ms 123888 KB Output is correct
35 Correct 924 ms 123740 KB Output is correct
36 Correct 1657 ms 137392 KB Output is correct
37 Correct 1653 ms 137288 KB Output is correct
38 Correct 1667 ms 136824 KB Output is correct
39 Correct 1679 ms 136776 KB Output is correct
40 Correct 1356 ms 133372 KB Output is correct
41 Correct 1337 ms 133452 KB Output is correct
42 Correct 1041 ms 132100 KB Output is correct
43 Correct 1058 ms 131848 KB Output is correct
44 Correct 249 ms 31156 KB Output is correct
45 Correct 246 ms 31220 KB Output is correct
46 Correct 255 ms 31116 KB Output is correct
47 Correct 227 ms 30164 KB Output is correct
48 Correct 232 ms 30216 KB Output is correct
49 Correct 239 ms 30144 KB Output is correct
50 Correct 161 ms 29900 KB Output is correct
51 Correct 161 ms 30004 KB Output is correct
52 Correct 138 ms 30024 KB Output is correct
53 Correct 146 ms 32064 KB Output is correct
54 Correct 234 ms 30996 KB Output is correct
55 Correct 241 ms 30992 KB Output is correct
56 Correct 232 ms 31040 KB Output is correct
57 Correct 239 ms 31056 KB Output is correct
58 Correct 227 ms 30944 KB Output is correct
59 Correct 242 ms 31052 KB Output is correct
60 Execution timed out 2096 ms 131332 KB Time limit exceeded
61 Halted 0 ms 0 KB -