oj.uz

Submission #881239

# Submission time Handle Problem Language Result Execution time Memory
881239 2023-12-01T00:50:52 Z yusuf12360 Sequence (APIO23_sequence) C++17
28 / 100
 2000 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;
}
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) {
	lazy[2*pos+1]+=lazy[pos];
	lazy[2*pos+2]+=lazy[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); lazy[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));
}
bool can(int k) {
	build();
	for(int val=1; val<=n; val++) {
		for(int p : pos[val]) update(p);
		for(int i=0; i+k-1<pos[val].size(); i++) {
			int l=pos[val][i], r=pos[val][i+k-1];
			int temp=get(r, r).mn;
			if(l) temp-=get(l-1, l-1).mx;
			int need=abs(temp)-k;
			if(need<=0) return 1;
			int add=0;
			if(l) {
				if(temp<0) add=get(l-1, l-1).mn-get(0, l-1).mn;
				else add=-get(l-1, l-1).mx+get(0, l-1).mx;
			}
			need-=add;
			if(need<=0) return 1;
			add=0;
			if(r+1<n) {
				if(temp<0) add=get(r+1, n-1).mx-get(r, r).mx;
				else add=-get(r+1, n-1).mn+get(r, r).mn;
			}
			need-=add;
			if(need<=0) return 1;
		}
		for(int p : pos[val]) update(p);
	}
	return 0;
}
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 l=1, r=n, ans=1;
	while(l<=r) {
		int mid=l+r>>1;
		if(can(mid)) ans=mid, l=mid+1;
		else r=mid-1;
	}
	return ans;
}

Compilation message

sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:33:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  push(pos); int mid=l+r>>1;
      |                     ~^~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  push(pos); int mid=l+r>>1;
      |                     ~^~
sequence.cpp: In function 'node build(int, int, int)':
sequence.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |  int mid=l+r>>1;
      |          ~^~
sequence.cpp: In function 'bool can(int)':
sequence.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0; i+k-1<pos[val].size(); i++) {
      |                ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:87:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mid=l+r>>1;
      |           ~^~

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 436 KB Output is correct
3 Correct 0 ms 436 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 0 ms 348 KB Output is correct
8 Correct 0 ms 344 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 0 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 436 KB Output is correct
3 Correct 0 ms 436 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 0 ms 348 KB Output is correct
8 Correct 0 ms 344 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 0 ms 348 KB Output is correct
13 Correct 6 ms 636 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 6 ms 600 KB Output is correct
16 Correct 7 ms 600 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 5 ms 664 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 6 ms 604 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 7 ms 632 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 Execution timed out 2029 ms 52572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Execution timed out 2028 ms 43524 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 2104 ms 58448 KB Time limit exceeded
2 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 436 KB Output is correct
3 Correct 0 ms 436 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 0 ms 348 KB Output is correct
8 Correct 0 ms 344 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 0 ms 348 KB Output is correct
13 Correct 6 ms 636 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 6 ms 600 KB Output is correct
16 Correct 7 ms 600 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 5 ms 664 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 6 ms 604 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 7 ms 632 KB Output is correct
23 Correct 551 ms 8740 KB Output is correct
24 Correct 542 ms 8744 KB Output is correct
25 Correct 553 ms 8788 KB Output is correct
26 Correct 455 ms 7648 KB Output is correct
27 Correct 509 ms 7516 KB Output is correct
28 Correct 517 ms 7776 KB Output is correct
29 Correct 411 ms 7260 KB Output is correct
30 Correct 397 ms 7316 KB Output is correct
31 Correct 265 ms 7636 KB Output is correct
32 Correct 436 ms 9976 KB Output is correct
33 Correct 415 ms 8784 KB Output is correct
34 Incorrect 511 ms 8572 KB Output isn't correct
35 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 436 KB Output is correct
3 Correct 0 ms 436 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 0 ms 348 KB Output is correct
8 Correct 0 ms 344 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 0 ms 348 KB Output is correct
13 Correct 6 ms 636 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 6 ms 600 KB Output is correct
16 Correct 7 ms 600 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 5 ms 664 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 6 ms 604 KB Output is correct
21 Correct 7 ms 604 KB Output is correct
22 Correct 7 ms 632 KB Output is correct
23 Execution timed out 2029 ms 52572 KB Time limit exceeded
24 Halted 0 ms 0 KB -