oj.uz

Submission #881264

# Submission time Handle Problem Language Result Execution time Memory
881264 2023-12-01T02:47:53 Z yusuf12360 Sequence (APIO23_sequence) C++17
20 / 100
 770 ms 58448 KB 
#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
struct node{
	int mn, mx;
	node(int mn=0, int mx=0) : mn(mn), mx(mx) {}
};
int n;
vector<vector<int>> pos;
vector<int> lazy;
vector<node> tr;
void change(int pos, int add) {
	tr[pos].mn+=add;
	tr[pos].mx+=add;
	lazy[pos]+=add;
}
node pull(node L, node R) {
	int mn, mx;
	mn=min(L.mn, R.mn);
	mx=max(L.mx, R.mx);
	return node(mn, mx);
}
void push(int pos) {
	change(2*pos+1, lazy[pos]);
	change(2*pos+2, lazy[pos]);
	lazy[pos]=0;
}
void update(int ll, int rr=n-1, int add=-1, int pos=0, int l=0, int r=n-1) {
	if(ll>rr) return;
	if(ll==l && rr==r) {change(pos, add); return;}
	push(pos); int mid=l+r>>1;
	update(ll, min(rr, mid), add, 2*pos+1, l, mid);
	update(max(mid+1, ll), rr, add, 2*pos+2, mid+1, r);
	tr[pos]=pull(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
	if(ll>rr) return node(INF, -INF);
	if(ll==l && rr==r) return tr[pos];
	push(pos); int mid=l+r>>1;
	return pull(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
node build(int pos=0, int l=0, int r=n-1) {
	lazy[pos]=0;
	if(l==r) return tr[pos]=node(l+1, r+1); 
	int mid=l+r>>1;
	return tr[pos]=pull(build(2*pos+1, l, mid), build(2*pos+2, mid+1, r));
}
int sequence(int N, vector<int> a) {
	n=N;
	pos.resize(n+1);
	tr.resize(4*n);
	lazy.resize(4*n);
	for(int i=0; i<n; i++) pos[a[i]].push_back(i);
	int ans=1;
	build();
	for(int val=1; val<=n; val++) {
		int idx=0;
		for(int p : pos[val]) update(p);
		for(int i=0; i<pos[val].size(); i++) {
			idx=max(idx, i);
			while(idx<pos[val].size()) {
				int mn=get(pos[val][idx], n-1).mn;
				if(pos[val][i]) mn-=max(0, get(0, pos[val][i]-1).mx);
				int mx=get(pos[val][idx], n-1).mx;
				if(pos[val][i]) mx-=min(0, get(0, pos[val][i]-1).mn);
				int len=idx-i+1;
				if(len<mn || -len>mx) break;
				else idx++; 
			}
			ans=max(ans, idx-i);
		}
		for(int p : pos[val]) update(p);
	}
	return ans;
}

Compilation message

sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  push(pos); int mid=l+r>>1;
      |                     ~^~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:40:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  push(pos); int mid=l+r>>1;
      |                     ~^~
sequence.cpp: In function 'node build(int, int, int)':
sequence.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid=l+r>>1;
      |          ~^~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i=0; i<pos[val].size(); i++) {
      |                ~^~~~~~~~~~~~~~~~
sequence.cpp:62:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    while(idx<pos[val].size()) {
      |          ~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 657 ms 51292 KB Output is correct
3 Correct 660 ms 52560 KB Output is correct
4 Correct 641 ms 42716 KB Output is correct
5 Correct 650 ms 51784 KB Output is correct
6 Correct 625 ms 51788 KB Output is correct
7 Correct 593 ms 43184 KB Output is correct
8 Correct 654 ms 43344 KB Output is correct
9 Correct 587 ms 43348 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 737 ms 43264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 744 ms 57160 KB Output is correct
2 Correct 751 ms 58448 KB Output is correct
3 Correct 770 ms 58076 KB Output is correct
4 Correct 762 ms 57940 KB Output is correct
5 Correct 752 ms 54528 KB Output is correct
6 Correct 760 ms 54460 KB Output is correct
7 Correct 706 ms 53308 KB Output is correct
8 Correct 716 ms 53196 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 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 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -