Submission #1114523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114523		epicci23	Sličnost (COI23_slicnost)	C++17	100 / 100	767 ms	48612 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;

struct LazySeg{
  vector<array<int,2>> seg;
  vector<int> Lazy;
 
  LazySeg(int n){
  	seg.resize(4*n+5);
  	Lazy.assign(4*n+5,0);
  	build(1,1,n);
  }

  inline array<int,2> merge(array<int,2> a,array<int,2> b){
    array<int,2> res;
    res[0]=max(a[0],b[0]);
    res[1]=0;
    if(res[0]==a[0]) res[1]+=a[1];
    if(res[0]==b[0]) res[1]+=b[1];
    return res;
  }

  inline void push(int rt, int l, int r){
  	if(Lazy[rt] == 0) return;
    int u = Lazy[rt];
    Lazy[rt] = 0;
    seg[rt][0] += u;
    if(l==r) return;
    Lazy[rt*2] += u;
    Lazy[rt*2+1] += u;
  }

  void build(int rt,int l,int r){
  	if(l==r){
  	  seg[rt]={0,1};
  	  return;
  	}
  	int m=(l+r)/2;
  	build(rt*2,l,m),build(rt*2+1,m+1,r);
  	seg[rt] = merge(seg[rt*2],seg[rt*2+1]);
  }

  void upd(int rt,int l,int r,int gl,int gr,int u){
  	push(rt,l,r);
  	if(r<gl || l>gr) return;
  	if(l>=gl && r<=gr){
  	  Lazy[rt] += u;
  	  push(rt,l,r);
  	  return;
  	}
  	int m = (l+r)/2;
  	upd(rt*2,l,m,gl,gr,u),upd(rt*2+1,m+1,r,gl,gr,u);
  	seg[rt] = merge(seg[rt*2],seg[rt*2+1]);
  }
};


struct Answer{
  vector<array<int,2>> seg,Lazy;

  Answer(int n){
  	seg.assign(4*n+5,{-1,0});
  	Lazy.assign(4*n+5,{-1,0});
  }

  inline array<int,2> merge(array<int,2> a,array<int,2> b){
    array<int,2> res;
    res[0]=max(a[0],b[0]);
    res[1]=0;
    if(res[0]==a[0]) res[1]+=a[1];
    if(res[0]==b[0]) res[1]+=b[1];
    return res;
  }
  
  inline void push(int rt, int l, int r){
    if(Lazy[rt][0] == -1) return;
    array<int,2> U = Lazy[rt];
    Lazy[rt] = {-1, 0};
    seg[rt] = merge(seg[rt],U);
    if(l==r) return;
    Lazy[rt*2] = merge(Lazy[rt*2],U);
    Lazy[rt*2+1] = merge(Lazy[rt*2+1],U);
  }

  void upd(int rt,int l,int r,int gl,int gr,array<int,2> u){
  	push(rt,l,r);
  	if(r<gl || l>gr) return;
  	if(l>=gl && r<=gr){
  	  Lazy[rt] = merge(Lazy[rt], u);
  	  push(rt,l,r);
  	  return;
  	}
    int m = (l + r) / 2;
    upd(rt*2,l,m,gl,gr,u),upd(rt*2+1,m+1,r,gl,gr,u);
  }
  
  array<int,2> get(int rt,int l,int r,int ind){
  	push(rt,l,r);
  	if(l==r) return seg[rt];
  	int m = (l+r)/2;
  	if(ind<=m) return get(rt*2,l,m,ind);
  	else return get(rt*2+1,m+1,r,ind);
  }
};


void _(){
  int n,k,q;
  cin >> n >> k >> q;
  int a[n+5],b[n+5],c[n+5];
  for(int i=1;i<=n;i++){
  	cin >> a[i];
  	c[i] = a[i];
  }
  for(int i=1;i<=n;i++) cin >> b[i];
  
  int ind[n+5];
  for(int i=1;i<=n;i++) ind[b[i]]=i;
  
  LazySeg T(n);
  Answer Ans(q+5);
  vector<int> delta[n+5];
  
  vector<array<int,2>> Versions[n+5];
  for(int i=1;i<=n;i++) Versions[i].push_back({0,a[i]});
 
  for(int i=1;i<=q;i++){
    int ind; cin >> ind;
    delta[ind].push_back(i);
    swap(c[ind],c[ind+1]);
    Versions[ind].push_back({i,c[ind]});
    Versions[ind+1].push_back({i,c[ind+1]});
  }

  auto Get_Val = [&](int ind,int ti){
    int it = lower_bound(all(Versions[ind]),array<int,2>{ti+1,-1}) - Versions[ind].begin();
    return Versions[ind][it-1][1];
  };
  
  for(int i=1;i<=n;i++){
    int p = ind[a[i]]; // open element
    T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),1);
    if(i<k) continue;

    if(i > k){ // close element
      p = ind[a[i-k]];
      T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),-1);
    }

    vector<array<int,2>> v;
  	for(int x:delta[i]) v.push_back({x,i});
  	if(i>k) for(int x:delta[i-k]) v.push_back({x,i-k+1});
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    int Time = 0;
    vector<array<int,2>> roll;
   
    // now time to do some updates and update answer array
    for(auto x:v){
      Ans.upd(1,0,q,Time,x[0]-1,T.seg[1]);
      Time = x[0];
      // close old value
      p = ind[Get_Val(x[1],x[0]-1)];
      T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),-1);
      roll.push_back({p,-1});
      // open new value
      p = ind[Get_Val(x[1],x[0])];
      T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),1);
      roll.push_back({p,1});
    }

    Ans.upd(1,0,q,Time,q,T.seg[1]);
    // rollback them
    while(!roll.empty()){
      auto xd = roll.back();
      roll.pop_back();
      p = xd[0];
      T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),-xd[1]);
    }
  }

  for(int i=0;i<=q;i++){
   auto U = Ans.get(1,0,q,i);
   cout << U[0] << ' ' << U[1] << '\n';
  }
}
int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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