QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#195449 | #2387. Min Max Convert | galen_colin# | RE | 0ms | 0kb | C++14 | 2.9kb | 2023-10-01 04:26:48 | 2023-10-01 04:26:49 |
answer
// comp = compile
// compr = compile & run
// in terminal, gocp goes to cp directory
#include <bits/stdc++.h>
using namespace std;
#include <bits/extc++.h>
using namespace __gnu_pbds;
using ll = long long;
using ordered_set = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using pl = pair<ll, ll>;
#define f first
#define s second
ll n;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
vector<ll> a(n), b(n);
for (ll &x: a) cin >> x;
for (ll &x: b) cin >> x;
vector<ll> nxt(n);
for (ll i = n - 1; i >= 0; i--){
if (i == n - 1 || b[i] != b[i + 1]) nxt[i] = i + 1;
else nxt[i] = nxt[i + 1];
}
ll pt = -1, last = -1;
vector<array<ll, 3>> ops;
for (ll i = 0; i < n; i++) {
if (last == b[i]) {
if (pt < i) {
ll r = i;
vector<pl> op;
op.push_back({i - 1, nxt[i] - 1});
ll lb = nxt[i];
for (ll j = i; j <= r; j++) {
if (lb < n && a[j] == b[lb]) {
op.push_back({j, nxt[lb] - 1});
r = lb;
lb = nxt[lb];
}
}
ll p = op.back().s;
ll ft = op.back().s + 1;
while (op.size()) {
pl x = op.back();
op.pop_back();
ll l = x.f, r = x.s;
// cout << l << " " << r << '\n';
for (ll p = l; p < r;) {
ll pr = p + 1;
if (p + 1 >= ft) pr = r;
if (a[p] < a[pr]) ops.push_back({'m', p, pr});
else if (a[p] > a[pr]) ops.push_back({'M', p, pr});
a[pr] = a[p];
p = pr;
}
ft = l;
}
i = p;
++pt;
}
continue;
}
if (pt < i) {
assert(pt == i - 1);
last = a[i];
++pt;
}
ll pr = pt;
while (pt < n && a[pt] != b[i]) ++pt;
if (pt == n) {
cout << -1 << '\n';
return 0;
}
for (ll t = pt; t - 1 > pr; t--) {
if (a[t - 1] < a[pt]) ops.push_back({'M', t - 1, pt});
else if (a[t - 1] > a[pt]) ops.push_back({'m', t - 1, pt});
}
if (last < a[pt]) ops.push_back({'M', i, pt});
else if (last > a[pt]) ops.push_back({'m', i, pt});
last = a[pt];
}
assert(ops.size() <= 2 * n);
cout << ops.size() << '\n';
for (auto x: ops) {
cout << ((char)x[0]) << " " << x[1] + 1 << " " << x[2] + 1 << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
100000 80159 24037 50544 49029 20937 95595 93373 58274 55943 97218 6019 21069 7470 92698 25184 8879 68760 75476 81465 87494 92468 11304 66134 85457 88083 59682 95187 18518 63052 61310 69855 4557 82231 40498 38847 95156 2291 94195 90442 94252 27042 63660 32300 25128 47881 8924 61749 44499 7315 93110 ...