제출 #1059653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059653		NeroZein	Sličnost (COI23_slicnost)	C++17	57 / 100	3096 ms	7812 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 ind[N]; 
long long lazy[N * 2];
pair<int, long long> seg[N * 2];

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

void build(int nd, int l, int r) {
  if (l == r) {
    seg[nd].second = 1;
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid);
  build(rs, mid + 1, r); 
  seg[nd] = combine(seg[nd + 1], seg[rs]); 
}

void push(int nd, int l, int r) {
  if (!lazy[nd]) {
    return;
  }
  seg[nd].first += lazy[nd];
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lazy[nd + 1] += lazy[nd];
    lazy[rs] += lazy[nd]; 
  }
  lazy[nd] = 0;
}

void upd(int nd, int l, int r, int s, int e, int v) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    lazy[nd] = v;
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    upd(nd + 1, l, mid, s, e, v); 
    push(rs, mid + 1, r); 
  } else {
    if (mid < s) {
      upd(rs, mid + 1, r, s, e, v);
      push(nd + 1, l, mid); 
    } else {
      upd(nd + 1, l, mid, s, e, v);
      upd(rs, mid + 1, r, s, e, v); 
    }
  }
  seg[nd] = combine(seg[nd + 1], seg[rs]);
}

void upd(int l, int r, int v) {
  if (l < n) {
    upd(0, 0, n - 1, l, min(n - 1, r), v); 
  }
}

pair<int, long long> qry(int nd, int l, int r, int s, int e) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    return seg[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e);
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e);
    } else {
      return combine(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
    }
  }
}

void solve(vector<int> a) {
  for (int i = 0; i < k; ++i) {
    upd(ind[a[i]], ind[a[i]] + k - 1, 1); 
  }
  pair<int, long long> ans; 
  for (int i = k - 1; i < n; ++i) {
    auto v = qry(0, 0, n - 1, k - 1, n - 1);
    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; 
  }
  build(0, 0, n - 1); 
  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: 33 / 33
• Subtask 4: 7 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33