#include <iostream>
using namespace std;
typedef long long ll;
pair <ll, ll> merge (pair <ll, ll> x, pair <ll, ll> y) {
if (x.first > y.first) return x;
if (x.first < y.first) return y;
return {x.first, x.second + y.second};
}
#define mid ((l + r) >> 1)
const int MAXN = 1e7 + 25;
int tl[MAXN], tr[MAXN], sum[MAXN], cnt;
pair <ll, ll> dp[MAXN];
int new_leaf (int x) {
cnt++; dp[cnt] = {0, 1};
return cnt;
}
int new_node (int l, int r) {
cnt++;
dp[cnt] = merge(dp[l], dp[r]);
tl[cnt] = l; tr[cnt] = r;
return cnt;
}
int build (int l, int r) {
if (l == r) {
return new_leaf(l);
} else {
return new_node(build(l, mid), build(mid + 1, r));
}
}
int update (int l, int r, int a, int b, int c, int node) {
if (l > b || r < a) return node;
if (l >= a && r <= b) {
cnt++; tl[cnt] = tl[node]; tr[cnt] = tr[node];
sum[cnt] = sum[node]; dp[cnt] = dp[node];
sum[cnt] += c; dp[cnt].first += c;
return cnt;
}
int x = update(l, mid, a, b, c, tl[node]);
int y = update(mid + 1, r, a, b, c, tr[node]);
cnt++;
tl[cnt] = x; tr[cnt] = y;
dp[cnt] = merge({dp[x].first + sum[node], dp[x].second}, {dp[y].first + sum[node], dp[y].second});
sum[cnt] = sum[node];
return cnt;
}
pair <ll, ll> get (int node) {
return dp[node];
}
int a[100002], n, k, q, p[100002];
int roots[100002];
struct SegmentTree2 {
pair <ll, ll> tree2[400001];
void build (int l, int r, int node) {
if (l == r) {
tree2[node] = {0, 1};
} else {
build(l, mid, 2 * node);
build(mid + 1, r, 2 * node + 1);
tree2[node] = merge(tree2[2 * node], tree2[2 * node + 1]);
}
}
void update (int l, int r, int a, pair <int, int> b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree2[node] = b;
return;
}
update(l, mid, a, b, 2 * node);
update(mid + 1, r, a, b, 2 * node + 1);
tree2[node] = merge(tree2[2 * node], tree2[2 * node + 1]);
}
} cur;
void val () {
cout << cur.tree2[1].first << " " << cur.tree2[1].second << '\n';
}
void solve () {
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
int x; cin >> x; p[x] = i;
}
for (int i = 1; i <= n; i++) {
a[i] = p[a[i]];
}
cur.build(1, n - k + 1, 1);
pair <ll, ll> dd = {-1, 0};
roots[1] = build(1, n);
for (int i = 1; i <= k; i++) {
roots[1] = update(1, n, max(1, a[i] - k + 1), min(a[i], n - k + 1), 1, roots[1]);
}
cur.update(1, n - k + 1, 1, get(roots[1]), 1);
for (int i = k + 1; i <= n; i++) {
roots[i - k + 1] = roots[i - k];
roots[i - k + 1] = update(1, n, max(1, a[i - k] - k + 1), min(a[i - k], n - k + 1), -1, roots[i - k + 1]);
roots[i - k + 1] = update(1, n, max(1, a[i] - k + 1), min(a[i], n - k + 1), 1, roots[i - k + 1]);
cur.update(1, n - k + 1, i - k + 1, get(roots[i - k + 1]), 1);
}
val();
while (q--) {
int t; cin >> t;
if (t + 1 <= n - k + 1) {
roots[t + 1] = update(1, n, max(1, a[t + 1] - k + 1), min(a[t + 1], n - k + 1), -1, roots[t + 1]);
roots[t + 1] = update(1, n, max(1, a[t] - k + 1), min(a[t], n - k + 1), 1, roots[t + 1]);
cur.update(1, n - k + 1, t + 1, get(roots[t + 1]), 1);
}
if (t - k + 1 >= 1) {
roots[t - k + 1] = update(1, n, max(1, a[t + 1] - k + 1), min(a[t + 1], n - k + 1), 1, roots[t - k + 1]);
roots[t - k + 1] = update(1, n, max(1, a[t] - k + 1), min(a[t], n - k + 1), -1, roots[t - k + 1]);
cur.update(1, n - k + 1, t - k + 1, get(roots[t - k + 1]), 1);
}
swap(a[t], a[t + 1]);
val();
}
}
signed main () {
#ifndef ONLINE_JUDGE
freopen("input_file", "r", stdin);
freopen("output_file", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:88:19: warning: variable 'dd' set but not used [-Wunused-but-set-variable]
88 | pair <ll, ll> dd = {-1, 0};
| ^~
Main.cpp: In function 'int main()':
Main.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen("input_file", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | freopen("output_file", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
