| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 468836 |
2021-08-29T19:41:14 Z |
mychecksedad |
Exam (eJOI20_exam) |
C++17 |
|
247 ms |
98932 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, K = 20;
#define pb push_back
int n, a[N], b[N], rmq[N][K];
map<int, vector<int>> m;
int subtask2(){
int ans = 0;
vector<bool> is_taken(n + 5, 0);
for(int i = 1; i <= n; i++){
if(a[i] == b[1]){
ans++;
int l = i-1, r = i + 1;
is_taken[i] = 1;
for(; l >= 1 && !is_taken[l] && a[l] < b[1]; l--) ans++, is_taken[l] = 1;
for(; r <= n && !is_taken[r] && a[r] < b[1]; r++) ans++, is_taken[r] = 1;
}
}
return ans;
}
int Q(int l, int r){
int k = __lg((r-l+1));
return max(rmq[l][k], rmq[r - (1<<k) + 1][k]);
}
int subtask4(){
map<int, int> m;
for(int i = 1; i <= n; i++) m[a[i]] = i;
vector<int> dp(n+2);
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
if(a[i] <= b[i]){
int pos = m[b[i]];
if(pos > 0 && Q(min(i, pos), max(i, pos)) <= b[i]){
dp[i]++;
}
}
}
return dp[n];
}
void precalc(){
for(int i = 1; i <= n; i++) rmq[i][0] = a[i];
for(int j = 1; j < K; j++){
for(int i = 1; i + (1<<j) <= n + 1; i++){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j - 1]);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
precalc();
bool is_b = 1;
for(int i = 2; i <= n; i++) if(b[i] != b[i - 1]) is_b = 0;
if(is_b){
cout << subtask2();
return 0;
}
if(n > 5000){
cout << subtask4();
return 0;
}
int ans = 0;
vector<vector<int>> dp(n+2, vector<int>(n+2));
for(int i = 1; i <= n; i++){
int mx = 0;
for(int j = 1; j <= n; j++){
int x = Q(min(i, j), max(i, j));
mx = max(mx, dp[i - 1][j]);
if(x > b[i]){
dp[i][j] = mx;
}else{
if(a[i] <= b[i] && a[j] == b[i]){
dp[i][j] = mx + 1;
}else dp[i][j] = mx;
}
if(i==n) ans=max(ans, dp[i][j]);
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1956 KB |
Output is correct |
| 3 |
Correct |
26 ms |
8012 KB |
Output is correct |
| 4 |
Correct |
25 ms |
8832 KB |
Output is correct |
| 5 |
Correct |
37 ms |
8912 KB |
Output is correct |
| 6 |
Correct |
31 ms |
8904 KB |
Output is correct |
| 7 |
Correct |
34 ms |
8896 KB |
Output is correct |
| 8 |
Correct |
36 ms |
8900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 3 |
Correct |
33 ms |
16204 KB |
Output is correct |
| 4 |
Correct |
194 ms |
91156 KB |
Output is correct |
| 5 |
Correct |
220 ms |
98932 KB |
Output is correct |
| 6 |
Correct |
203 ms |
98756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
516 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 9 |
Correct |
33 ms |
16204 KB |
Output is correct |
| 10 |
Correct |
194 ms |
91156 KB |
Output is correct |
| 11 |
Correct |
220 ms |
98932 KB |
Output is correct |
| 12 |
Correct |
203 ms |
98756 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
516 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
460 KB |
Output is correct |
| 21 |
Correct |
1 ms |
460 KB |
Output is correct |
| 22 |
Correct |
9 ms |
4300 KB |
Output is correct |
| 23 |
Correct |
2 ms |
716 KB |
Output is correct |
| 24 |
Correct |
228 ms |
98756 KB |
Output is correct |
| 25 |
Correct |
216 ms |
98856 KB |
Output is correct |
| 26 |
Correct |
199 ms |
98848 KB |
Output is correct |
| 27 |
Correct |
201 ms |
98852 KB |
Output is correct |
| 28 |
Correct |
247 ms |
98844 KB |
Output is correct |
| 29 |
Correct |
233 ms |
98848 KB |
Output is correct |
| 30 |
Correct |
220 ms |
98844 KB |
Output is correct |
| 31 |
Correct |
211 ms |
98864 KB |
Output is correct |
| 32 |
Correct |
204 ms |
98748 KB |
Output is correct |
