Submission #1189507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189507		mychecksedad	Sličnost (COI23_slicnost)	C++20	34 / 100	294 ms	356120 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 3e7+10, MX = 30;

int K, nxt = 1;
struct Node{
  int L, R;
  int lazy, mx, cnt;
} C[M];

void reset(int v){C[v].L=C[v].R=0;}
void reset(int v, int pos){
  C[v].lazy = C[v].mx = 0;
  if(pos < K) C[v].cnt = 0;
  else C[v].cnt = 1;
}
void reset(int v, int l, int r){
  C[v].L = l, C[v].R = r;
  C[v].lazy = 0;
  if(C[C[v].L].mx > C[C[v].R].mx){
    C[v].mx = C[C[v].L].mx;
    C[v].cnt = C[C[v].L].cnt;
  }else if(C[C[v].R].mx > C[C[v].L].mx){
    C[v].mx = C[C[v].R].mx;
    C[v].cnt = C[C[v].R].cnt;
  }else{
    C[v].mx = C[C[v].L].mx;
    C[v].cnt = C[C[v].L].cnt + C[C[v].R].cnt;
  }
}
void reset(int v, int lazyy, int mxx, int cntt, int l, int r){
  C[v].L = l, C[v].R = r;
  C[v].cnt=cntt;
  C[v].lazy=lazyy;
  C[v].mx=mxx;
}
void push(int v){
  int l = C[v].L, r = C[v].R;
  C[v].L = nxt++; C[v].R = nxt++;
  reset(C[v].L, C[l].lazy + C[v].lazy, C[l].mx + C[v].lazy, C[l].cnt, C[l].L, C[l].R);
  reset(C[v].R, C[r].lazy + C[v].lazy, C[r].mx + C[v].lazy, C[r].cnt, C[r].L, C[r].R);
  C[v].lazy = 0;
}


int n, q, a[N], b[N], pos[N], c[N];


int build(int l, int r){
  if(l == r){
    int pos = nxt++;
    reset(pos, l);
    return pos;
  }
  int mid=l+r>>1;
  int pos = nxt++;
  reset(pos, build(l, mid), build(mid+1, r));
  return pos; 
}
int upd(int v, int l, int r, int ql, int qr, int val){
  if(ql > r || l > qr) return v;
  if(ql <= l && r <= qr){
    int pos = nxt++;
    reset(pos, C[v].lazy + val, C[v].mx + val, C[v].cnt, C[v].L, C[v].R);
    return pos;
  }
  push(v);
  int mid = l+r>>1;
  int pos = nxt++;
  reset(pos, upd(C[v].L, l, mid, ql, qr, val), upd(C[v].R, mid+1, r, ql, qr, val));
  return pos;
}
void solve(){
  cin >> n >> K >> q;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  for(int i = 1; i <= n; ++i){
    cin >> b[i];
    pos[b[i]] = i;
  }
  for(int i = 1; i <= n; ++i){
    c[i] = pos[a[i]];
  }
  vector<int> roots;
  roots.pb(build(1, n));
  vector<int> CNT(n + 1); // mx, count
  multiset<int> S;
  for(int i = 1; i <= n; ++i){
    roots.pb(upd(roots.back(), 1, n, max(K, c[i]), min(n, c[i] + K - 1), 1));
    if(i > K){
      roots.back() = upd(roots.back(), 1, n, max(K, c[i - K]), min(n, c[i - K] + K - 1), -1);
    }
    if(i >= K){
      CNT[C[roots.back()].mx] += C[roots.back()].cnt;
      S.insert(C[roots.back()].mx);
      // cout << C[roots.back()].mx << ' ' << C[roots.back()].cnt << '\n';
    }
  }
  cout << *prev(S.end()) << ' ' << CNT[(*prev(S.end()))] << '\n';
  for(int j = 0; j < q; ++j){
    int p; cin >> p;
    swap(a[p], a[p + 1]);
    c[p] = pos[a[p]];
    c[p + 1] = pos[a[p + 1]];
    if(p >= K){
      CNT[C[roots[p]].mx] -= C[roots[p]].cnt;
      S.erase(S.find(C[roots[p]].mx));
    }
    roots[p] = upd(roots[p - 1], 1, n, max(K, c[p]), min(n, c[p] + K - 1), 1);
    if(p > K){
      roots[p] = upd(roots[p], 1, n, max(K, c[p - K]), min(n, c[p - K] + K - 1), -1);
    }

    if(p >= K){
      CNT[C[roots[p]].mx] += C[roots[p]].cnt;
      S.insert(C[roots[p]].mx); 
    }

    p += K;

    if(p <= n){
      CNT[C[roots[p]].mx] -= C[roots[p]].cnt;
      S.erase(S.find(C[roots[p]].mx));

      roots[p] = upd(roots[p - 1], 1, n, max(K, c[p]), min(n, c[p] + K - 1), 1);
      if(p > K){
        roots[p] = upd(roots[p], 1, n, max(K, c[p - K]), min(n, c[p - K] + K - 1), -1);
      }
      CNT[C[roots[p]].mx] += C[roots[p]].cnt;
      S.insert(C[roots[p]].mx);
    }
    cout << *prev(S.end()) << ' ' << CNT[(*prev(S.end()))] << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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