Submission #1319685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319685		WH8	Sličnost (COI23_slicnost)	C++17	0 / 100	357 ms	589824 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iii tuple<int,int,int>
#define eb emplace_back

int n,k,q;
const pll sen={0, 0};
struct Node {
       pll v;
	   int s,e,m,lz;
       Node *l, *r;
       Node (int S,int E){
              s=S; e=E;
              if(s+e>=0) m=(s+e)/2;
              else m=(s+e-1)/2;
			  v={0ll,e-s+1};
			  lz=0;
              l=r=nullptr;
       }
	   void prop(){
		   if(lz==0)return;
		   if(l){
			   l->v.f+=lz;
			   l->lz+=lz;
		   }
		   if(r){
			   r->v.f+=lz;
			   r->lz+=lz;
		   }
	   }
} * roots[100005];

Node* dupe(Node *node){
       Node* ret=new Node(node->s,node->e);
       ret->v=node->v;
       ret->l=node->l; ret->r=node->r;
	   ret->lz=node->lz;
       return ret;
}
pll combine(pll a, pll b){
	if(a.f == b.f) return mp(a.f, a.s + b.s);
	else return max(a, b);
}
void update(Node * node, int S, int E, int V){ // pass pointer *
       int & s=node->s, & m=node->m, &e=node->e, &lz=node->lz;
	   pll &v=node->v;
       Node* &l=node->l;
       Node* &r= node->r;
       if(s==S and e==E){
		v.f += V;
		lz+=V;
              return;
       }
	   node->prop();
       if(E<=m){
              if(!l) l=new Node(s,m);
              else l=dupe(l);
              update(l, S,E,V);
       }
       else if(S > m){
              if(!r) r=new Node(m+1,e);
              else r=dupe(r);
              update(r,S,E,V);
       }
	   else {
		  if(!l) l=new Node(s,m);
		  else l=dupe(l);
		  update(l, S,m,V);
		  if(!r) r=new Node(m+1,e);
		  else r=dupe(r);
		  update(r, m+1,E,V);
		}
	   v=combine((l?l->v:sen), (r?r->v:sen));
       //~ printf("SEGMENT %lld to %lld, count %lld, sum %lld\n",s,e,count,sum);
}

signed main(){
	cin>>n>>k>>q;
	vector<int> a(n+1,0), b(n+1, 0);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		int c;cin>>c;
		b[c]=i;
	}
	for(int i=1;i<=n;i++)a[i]=b[a[i]];
	map<int,int> mappa;
	roots[k]=new Node(1, n);
	for(int i=1;i<=k;i++){
		update(roots[k], a[i]-k+1, a[i], 1);
	}
	mappa[roots[k]->v.f] += roots[k]->v.s;
	for(int i=k+1;i<=n;i++){
		roots[i]=dupe(roots[i-1]);
		update(roots[i], a[i-k]-k+1, a[i-k], -1);
		update(roots[i], a[i]-k+1, a[i], 1);
		mappa[roots[i]->v.f] += roots[i]->v.s;
	}

	auto [l, c] = *(prev(mappa.end()));
	cout<<l<<" "<<c<<'\n';
	while(q--){
		int a,b;cin>>a>>b;
		cout<<l<<" "<<c<<'\n';
	}
}

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