| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 452056 |
2021-08-03T17:14:00 Z |
fskarica |
Exam (eJOI20_exam) |
C++14 |
|
3 ms |
460 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
const int MAX = 2020;
int n;
int x, y;
int v, pos;
int a, b;
int arra[MAX];
int arrb[MAX];
int prf[MAX];
int prfmax[MAX];
int suf[MAX];
int sufmax[MAX];
vector <pii> ve;
void clean() {
for (int i = 0; i <= n + 1; i++) {
prf[i] = 0;
prfmax[i] = 0;
suf[i] = 0;
sufmax[i] = 0;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arra[i];
ve.push_back({arra[i], i});
}
for (int i = 1; i <= n; i++) {
cin >> arrb[i];
}
sort(ve.begin(), ve.end());
for (auto e : ve) {
// cout << e.fi << " " << e.se << "\n";
clean();
v = e.fi;
a = e.se;
pos = a + 1;
while (1) {
if (pos > n) break;
if (arra[pos] >= v) break;
pos++;
}
pos--;
// cout << a << " " << pos << "\n";
for (int i = a + 1; i <= pos; i++) {
prf[i - a] = prf[i - a - 1];
if (arra[i] == arrb[i]) prf[i - a]--;
if (v == arrb[i]) prf[i - a]++;
}
for (int i = pos; i >= a + 1; i--) {
suf[i - a] = suf[i - a + 1];
if (arra[i] == arrb[i]) suf[i - a]--;
if (v == arrb[i]) suf[i - a]++;
}
for (int i = 1; i <= pos - a; i++) prfmax[i] = max(prfmax[i - 1], prf[i]);
for (int i = pos - a; i >= 1; i--) sufmax[i] = max(sufmax[i + 1], suf[i]);
if (arra[pos + 1] == arra[a]) {
// cout << "uso11\n";
// for (int i = 1; i <= pos - a; i++) cout << prf[i] << " "; cout << " !\n";
// for (int i = 1; i <= pos - a; i++) cout << prfmax[i] << " "; cout << " !\n";
// for (int i = 1; i <= pos - a; i++) cout << suf[i] << " "; cout << " !\n";
// for (int i = 1; i <= pos - a; i++) cout << sufmax[i] << " "; cout << " !\n";
x = 0;
y = 0;
for (int i = 1; i <= pos - a; i++) {
if (prfmax[i] + sufmax[i + 1] > x + y) {
x = prfmax[i];
y = sufmax[i + 1];
}
}
// cout << x << " " << y << " x y\n";
for (int i = a + 1; i <= pos; i++) {
arra[i] = v;
if (prf[i - a] == x) break;
}
for (int i = pos; i >= a + 1; i--) {
arra[i] = v;
if (suf[i - a] == y) break;
}
}
else {
x = prfmax[pos - a];
for (int i = a + 1; i <= pos; i++) {
if (x == 0) break;
arra[i] = v;
if (prf[i - a] == x) break;
}
}
/////////////////////////////////////
clean();
v = e.fi;
a = e.se;
pos = a - 1;
while (1) {
if (pos < 1) break;
if (arra[pos] >= v) break;
pos--;
}
pos++;
swap(pos, a);
pos--;
a--;
// cout << a << " " << pos << "\n";
for (int i = a + 1; i <= pos; i++) {
prf[i - a] = prf[i - a - 1];
if (arra[i] == arrb[i]) prf[i - a]--;
if (v == arrb[i]) prf[i - a]++;
}
for (int i = pos; i >= a + 1; i--) {
suf[i - a] = suf[i - a + 1];
if (arra[i] == arrb[i]) suf[i - a]--;
if (v == arrb[i]) suf[i - a]++;
}
for (int i = 1; i <= pos - a; i++) prfmax[i] = max(prfmax[i - 1], prf[i]);
for (int i = pos - a; i >= 1; i--) sufmax[i] = max(sufmax[i + 1], suf[i]);
if (arra[pos + 1] == arra[a]) {
// cout << "uso12\n";
// for (int i = 1; i <= pos - a; i++) cout << prf[i] << " "; cout << " !\n";
// for (int i = 1; i <= pos - a; i++) cout << prfmax[i] << " "; cout << " !\n";
// for (int i = 1; i <= pos - a; i++) cout << suf[i] << " "; cout << " !\n";
// for (int i = 1; i <= pos - a; i++) cout << sufmax[i] << " "; cout << " !\n";
x = 0;
y = 0;
for (int i = 1; i <= pos - a; i++) {
if (prfmax[i] + sufmax[i + 1] > x + y) {
x = prfmax[i];
y = sufmax[i + 1];
}
}
for (int i = a + 1; i <= pos; i++) {
arra[i] = v;
if (prf[i - a] == x) break;
}
for (int i = pos; i >= a + 1; i--) {
arra[i] = v;
if (suf[i - a] == y) break;
}
}
else {
// cout << "uso22\n";
// for (int i = 1; i <= pos - a; i++) cout << prf[i] << " "; cout << "\n";
// for (int i = 1; i <= pos - a; i++) cout << prfmax[i] << " "; cout << "\n";
// for (int i = 1; i <= pos - a; i++) cout << suf[i] << " "; cout << "\n";
// for (int i = 1; i <= pos - a; i++) cout << sufmax[i] << " "; cout << "\n";
x = sufmax[1];
for (int i = pos; i >= a + 1; i--) {
if (x == 0) break;
arra[i] = v;
if (suf[i - a] == x) break;
}
}
// for (int i = 1; i <= n; i++) {
// cout << arra[i] << " ";
// }
// cout << "\n";
// cout << "\n";
}
int sol = 0;
for (int i = 1; i <= n; i++) {
if (arra[i] == arrb[i]) sol++;
}
cout << sol << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 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 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
