Submission #1312389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312389		repmann	Sličnost (COI23_slicnost)	C++20	50 / 100	104 ms	4268 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];
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;
  Setup();
  map <int, ll> MAP;
  for(int i = 1; i <= K; i++) Add(max(I[A[i]] - K + 1, 1), min(I[A[i]], N - K + 1), +1);
//  cout << ST[1].mx << ' ' << ST[1].cnt << '\n';
  MAP[ST[1].mx] += ST[1].cnt;
  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);
//    cout << ST[1].mx << ' ' << ST[1].cnt << '\n';
    Add(max(I[A[i]] - K + 1, 1), min(I[A[i]], N - K + 1), +1);
//    cout << ST[1].mx << ' ' << ST[1].cnt << '\n';
    MAP[ST[1].mx] += ST[1].cnt;
  }
  cout << MAP.rbegin()->first << ' ' << MAP.rbegin()->second << '\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