Submission #1312403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312403		repmann	Sličnost (COI23_slicnost)	C++20	50 / 100	124 ms	10896 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, W, K, Q;
int A[100001], B[100001], I[100001], MX[100001], CNT[100001];
ll SUM[100001];
int QR[100001];
vector <array <int, 4>> V[100001];
vector <array <int, 3>> T[100001];
struct Node
{
  int mx, cnt, p;
}ST[400001];
inline void Merge(int i)
{
  if(i >= W) return;
  ST[i].mx = max(ST[i << 1].mx, ST[i << 1 | 1].mx);
  ST[i].cnt = 0;
  ST[i].cnt += (ST[i << 1].mx == ST[i].mx) * ST[i << 1].cnt;
  ST[i].cnt += (ST[i << 1 | 1].mx == ST[i].mx) * ST[i << 1 | 1].cnt;
  return;
}
inline void Setup()
{
  W = 1;
  while(W < (N - K + 1)) W <<= 1;
  for(int i = 1; i <= (N - K + 1); i++) ST[i + W - 1] = {0, 1, 0};
  for(int i = W - 1; i; i--) Merge(i);
  return;
}
inline void Propagate(int i)
{
  if(!ST[i].p) return;
  if(i < W)
  {
    ST[i << 1].p += ST[i].p;
    ST[i << 1 | 1].p += ST[i].p;
  }
  ST[i].mx += ST[i].p;
  ST[i].p = 0;
  return;
}
inline void Add(int l, int r, int x, int i = 1, int lc = 1, int rc = W)
{
  Propagate(i);
  if((l > rc) || (lc > r)) return;
  if((l <= lc) && (rc <= r)) {ST[i].p += x; return Propagate(i);}
  int s = (lc + rc) >> 1;
  Add(l, r, x, i << 1, lc, s);
  Add(l, r, x, i << 1 | 1, s + 1, rc);
  Merge(i);
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> K >> Q;
  for(int i = 1; i <= N; i++) cin >> A[i];
  for(int i = 1; i <= N; i++) cin >> B[i];
  for(int i = 1; i <= N; i++) I[B[i]] = i;
  for(int i = 1; i <= Q; i++)
  {
    cin >> QR[i];
    if(I[A[QR[i]]] >= K)
    {
      V[QR[i] - K + 1].push_back({max(I[A[QR[i]]] - K + 1, 1), min(I[A[QR[i]]], N - K + 1), -1, i});
      if(I[A[QR[i] + 1]] <= (N - K + 1)) V[QR[i] - K + 1].push_back({max(I[A[QR[i] + 1]] - K + 1, 1), min(I[A[QR[i] + 1]], N - K + 1), +1, +i});
      else V[QR[i] - K + 1].push_back({max(I[A[QR[i] + 1]] - K + 1, 1), min(I[A[QR[i] + 1]], N - K + 1), +1, -i});
    }
    if(I[A[QR[i] + 1]] <= (N - K + 1))
    {
      V[QR[i] + 1].push_back({max(I[A[QR[i] + 1]], 1), min(I[A[QR[i] + 1]], N - K + 1), -1, i});
      V[QR[i] + 1].push_back({max(I[A[QR[i]]], 1), min(I[A[QR[i]]], N - K + 1), +1, -i});
    }
    swap(A[QR[i]], A[QR[i] + 1]);
//    for(int i = 1; i <= N; i++) cout << A[i] << " \n"[i == N];
  }
  for(int i = Q; i >= 1; i--) swap(A[QR[i]], A[QR[i] + 1]);
//  for(int i = 1; i <= N; i++) cout << A[i] << " \n"[i == N];
  Setup();
  auto compute = [&](int i)
  {
    T[0].push_back({ST[1].mx, ST[1].cnt, i});
//    cout << i << ":\n";
    for(auto x : V[i])
    {
//      cout << x[0] << ' ' << x[1] << ' ' << x[2] << ' ' << x[3] << '\n';
      Add(x[0], x[1], +x[2]);
      if(x[3] < 0) T[-x[3]].push_back({ST[1].mx, ST[1].cnt, i});
    }
    reverse(V[i].begin(), V[i].end());
    for(auto x : V[i]) Add(x[0], x[1], -x[2]);
    return;
  };
  for(int i = 1; i <= K; i++) Add(max(I[A[i]] - K + 1, 1), min(I[A[i]], N - K + 1), +1);
  compute(1);
  for(int i = K + 1; i <= N; i++)
  {
    Add(max(I[A[i - K]] - K + 1, 1), min(I[A[i - K]], N - K + 1), -1);
    Add(max(I[A[i]] - K + 1, 1), min(I[A[i]], N - K + 1), +1);
    compute(i - K + 1);
  }
  set <pair <int, int>> SET;
  for(int i = 1; i <= (N - K + 1); i++) SET.insert({0, i});
  SUM[0] = N - K + 1;
  for(int i = 0; i <= Q; i++)
  {
//    cout << i << ":\n";
    for(auto x : T[i])
    {
      SET.erase({MX[x[2]], x[2]});
      SET.insert({x[0], x[2]});
      SUM[MX[x[2]]] -= CNT[x[2]];
      SUM[MX[x[2]] = x[0]] += (CNT[x[2]] = x[1]);
//      cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
    }
    cout << SET.rbegin()->first << ' ' << SUM[SET.rbegin()->first] << '\n';
  }

  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 33 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33