# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
842160 |
2023-09-02T13:00:24 Z |
konber |
Exam (eJOI20_exam) |
C++14 |
|
250 ms |
4832 KB |
#include <iostream>
#include <vector>
using namespace std;
vector<int> A, b, st;
int N;
void build(int p, int L, int R){
if(L==R){
st[p] = A[L];
return;
}
build(2*p, L, (L+R)/2);
build(2*p+1, (L+R)/2+1, R);
st[p] = max(st[2*p], st[2*p+1]);
}
int rmq(int p, int L, int R, int i, int j){
if(j < L || i > R) return -1;
if(L >= i && R <= j) return st[p];
int mid=(L+R)/2;
return max(rmq(2*p, L, mid, i, j), rmq(2*p+1, mid+1, R, i, j));
}
int f(vector<int> a, int i){
if(i==N){
int ans=0;
for(int j=0; j < N; j++) ans += a[j]==b[j];
return ans;
}
int j=i, k=i;
bool changes=true;
vector<int> a1=a, a2=a;
while(changes){
changes = false;
if(j >= 0 && a[j] <= b[i]){
a1[j] = b[i];
changes=true;
j--;
}
if(k <= N-1 && a[k] <= b[i]){
a2[k] = b[i];
changes=true;
k++;
}
if(j==0 && k==N-1) break;
}
return max(f(a, i+1), max(f(a1, i+1), f(a2, i+1)));
}
int main()
{
scanf("%d", &N);
A.resize(N);
b.resize(N);
st.resize(4*N);
for(int i=0; i < N; i++)
scanf("%d", &A[i]);
for(int i=0; i < N; i++)
scanf("%d", &b[i]);
if(N <= 10){
cout << f(A, 0) << endl;
}
else{
build(1, 0, N-1);
int s=0, i=0;
while(i < N){
int first=i, last=N-1, ans=i, mid;
while(first <= last){
mid = (first+last)/2;
int m = rmq(1, 0, N-1, i, mid);
if(m > b[0]) last = mid-1;
else{
ans = mid;
first = mid+1;
}
}
if(rmq(1, 0, N-1, i, ans)==b[0]) s += ans-i+1;
i = ans+1;
}
printf("%d\n", s);
}
}
Compilation message
exam.cpp: In function 'int main()':
exam.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
exam.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
exam.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d", &b[i]);
| ~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
4 ms |
1116 KB |
Output is correct |
3 |
Correct |
138 ms |
3420 KB |
Output is correct |
4 |
Correct |
14 ms |
3164 KB |
Output is correct |
5 |
Correct |
19 ms |
4692 KB |
Output is correct |
6 |
Correct |
250 ms |
3168 KB |
Output is correct |
7 |
Correct |
14 ms |
3164 KB |
Output is correct |
8 |
Correct |
240 ms |
4832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |