Submission #1059637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059637		NeroZein	Sličnost (COI23_slicnost)	C++17	24 / 100	3057 ms	3420 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5; 

int n, k;

int ps[N];
int ind[N]; 

void upd(int l, int r, int v) {
  for (int i = l; i <= min(n - 1, r); ++i) {
    ps[i] += v; 
  }
}

pair<int, int> combine(pair<int, int> x, pair<int, int> y) {
  if (x.first < y.first) swap(x, y);
  if (x.first == y.first) {
    x.second += y.second;
  }
  return x; 
}

pair<int, int> qry() {
  pair<int, int> ret; 
  //for (int i = 0; i < n; ++i) {
    //debug(i, ps[i]); 
  //}
  for (int i = k - 1; i < n; ++i) {
    ret = combine(ret, make_pair(ps[i], 1)); 
  }
  return ret; 
}

void solve(vector<int> a) {
  for (int i = 0; i < k; ++i) {
    upd(ind[a[i]], ind[a[i]] + k - 1, 1); 
  }
  pair<int, int> ans; 
  for (int i = k - 1; i < n; ++i) {
    auto v = qry();
    ans = combine(ans, v);
    upd(ind[a[i - k + 1]], ind[a[i - k + 1]] + k - 1, -1);
    if (i + 1 < n) {
      upd(ind[a[i + 1]], ind[a[i + 1]] + k - 1, 1);       
    }
  }
  for (int i = n - k + 1; i < n; ++i) {
    upd(ind[a[i]], ind[a[i]] + k - 1, -1); 
  }
  cout << ans.first << ' ' << ans.second << '\n'; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q;
  cin >> n >> k >> q;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<int> b(n); 
  for (int i = 0; i < n; ++i) {
    cin >> b[i]; 
    ind[b[i]] = i; 
  }
  solve(a); 
  while (q--) {
    int t;
    cin >> t;
    swap(a[t - 1], a[t]); 
    solve(a); 
  }
  return 0;
}

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