#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXS 500
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
int mx;
ll cnt;
node(int x = 0) :mx(x), cnt(1) {}
};
node operator+(node n1, node n2) {
node ret;
ret.mx = max(n1.mx, n2.mx);
ret.cnt = 0;
if (ret.mx == n1.mx) ret.cnt += n1.cnt;
if (ret.mx == n2.mx) ret.cnt += n2.cnt;
return ret;
}
node operator+(node n, ll x) {
node ret = n;
ret.mx += x;
return ret;
}
namespace segtree {
node tree[MAX];
int lazy[MAX];
int N;
void init(int s, int e, int loc = 1) {
lazy[loc] = 0;
if (s == e) {
tree[loc] = node();
return;
}
int m = s + e >> 1;
init(s, m, loc * 2);
init(m + 1, e, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void prop(int loc) {
for (auto c : { loc * 2, loc * 2 + 1 }) {
tree[c] = tree[c] + lazy[loc];
lazy[c] += lazy[loc];
}
lazy[loc] = 0;
}
void upd(int s, int e, int l, int r, ll x, int loc = 1) {
if (l < 1) l = 1;
if (r > N) r = N;
if (l > r) return;
if (s != e) prop(loc);
if (e < l || r < s) return;
if (l <= s && e <= r) {
tree[loc] = tree[loc] + x;
lazy[loc] += x;
return;
}
int m = s + e >> 1;
upd(s, m, l, r, x, loc * 2);
upd(m + 1, e, l, r, x, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
};
int N, K, Q;
int A[MAX];
int B[MAX];
int rb[MAX];
node calc() {
int i;
node res(0);
for (i = 1; i <= N; i++) rb[B[i]] = i;
segtree::N = N - K + 1;
segtree::init(1, N - K + 1);
for (i = 1; i <= N; i++) {
segtree::upd(1, N - K + 1, rb[A[i]] - K + 1, rb[A[i]], 1);
if (i > K) segtree::upd(1, N - K + 1, rb[A[i - K]] - K + 1, rb[A[i - K]], -1);
if (i >= K) res = res + segtree::tree[1];
}
return res;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> K >> Q;
int i;
//for (i = 1; i <= N; i++) cin >> A[i];
//for (i = 1; i <= N; i++) cin >> B[i];
for (i = 1; i <= N; i++) A[i] = i;
for (i = 1; i <= N; i++) B[i] = i;
auto res = calc();
cout << res.mx << bb << res.cnt << ln;
while (Q--) {
int k;
cin >> k;
swap(A[k], A[k + 1]);
auto res = calc();
cout << res.mx << bb << res.cnt << ln;
}
}
Compilation message
Main.cpp: In function 'void segtree::init(int, int, int)':
Main.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int m = s + e >> 1;
| ~~^~~
Main.cpp: In function 'void segtree::upd(int, int, int, int, ll, int)':
Main.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int m = s + e >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
16084 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
16084 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
16084 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
16084 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
16084 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
16084 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
