Submission #1114266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114266		epicci23	Sličnost (COI23_slicnost)	C++17	50 / 100	137 ms	13136 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);
  }

  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]);
  }
 
};



void _(){
  int n,k,q;
  cin >> n >> k >> q;
  int a[n+5],b[n+5];
  for(int i=1;i<=n;i++) cin >> a[i];
  for(int i=1;i<=n;i++) cin >> b[i];
  
  int ind[n+5],mx=-1,ans=0;
  for(int i=1;i<=n;i++) ind[b[i]]=i;
  
  LazySeg T(n);

  for(int i=1;i<=n;i++){
  	// open number
    int p = ind[a[i]];
    // cout << "p: " << p << '\n';
    T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),1);
    // remove number
    if(i > k){
      p = ind[a[i-k]];
      T.upd(1,1,n,max(1LL,p-k+1),min(n-k+1,p),-1);
    }

    array<int,2> cur = T.seg[1];
    if(cur[0] < mx) continue;
    if(cur[0] > mx){
      mx = cur[0];
      if(i>=k) ans = cur[1];
    }
    else if(i>=k) ans+=cur[1];

    // cout << mx << ' ' << ans << '\n';
  }

  cout << mx << ' ' << ans << '\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: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33