제출 #1319740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319740		WH8	Sličnost (COI23_slicnost)	C++17	17 / 100	459 ms	589824 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#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 or (s==e))return;
			if(!l)l=new Node(s, m);
			else l=dupe(l);
		   l->v.f+=lz;
		   l->lz+=lz;
			if(!r)r=new Node(m+1, e);
			else r=dupe(r);
		   r->v.f+=lz;
		   r->lz+=lz;
		   lz=0;
	   }
	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;
	}
} * 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) or (s==e)){
		v.f += V;
		lz+=V;
       //printf("SEGMENT %d to %d, v.f %d, v.s %d\n",s,e,v.f, v.s);
              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:mp(0ll, m-s+1)), (r?r->v:mp(0ll, e-m)));
       //printf("SEGMENT %d to %d, v.f %d, v.s %d\n",s,e,v.f, v.s);
}

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]];
		//printf("a[%d] is %d\n", i, a[i]);
	}
	map<int,int> mappa;
	roots[k]=new Node(1, n);
	for(int i=1;i<=k;i++){
		//for (int j=a[i];j<=min(n, a[i]+k-1);j++) update(roots[k], j, j, 1);
		//if(a[i] <= n-k+1) 
		update(roots[k], max(k, a[i]), min(n,a[i]+k-1), 1);
	}
	mappa[roots[k]->v.f] += roots[k]->v.s;
	//printf("%lld, %lld\n",roots[k]->v.f, roots[k]->v.s);
	for(int i=k+1;i<=n;i++){
		roots[i]=dupe(roots[i-1]);
		//for (int j=a[i-k];j<=min(n, a[i-k]+k-1);j++) update(roots[i], j, j, -1);
		//if (a[i-k] <= n-k+1) 
		update(roots[i], max(k,a[i-k]), min(n,a[i-k]+k-1), -1);
		//for (int j=a[i];j<=min(n, a[i]+k-1);j++) update(roots[i], j, j, 1);
		//if (a[i] <= n-k+1)
		update(roots[i], max(k,a[i]), min(n, a[i]+k-1), 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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 0 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33