Submission #1319746

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

Main

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#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;
using pll = pair<int,int>; // (maxValue, count)

// combine: pick larger max; if tie, add counts
static inline pll combine(pll a, pll b){
    if(a.first == b.first) return {a.first, a.second + b.second};
    return (a.first > b.first ? a : b);
}

struct Node {
    int s, e, m;
    int lz;
    pll v;
    Node *l, *r;

    Node(int S, int E): s(S), e(E), lz(0), l(nullptr), r(nullptr) {
        m = (s + e) / 2;
        v = {0, e - s + 1}; // all zeros => max=0, count=segment length
    }
} *roots[100005];

// clone exactly once
static inline Node* clone(Node* t){
    Node* c = new Node(t->s, t->e);
    c->m  = t->m;
    c->lz = t->lz;
    c->v  = t->v;
    c->l  = t->l;
    c->r  = t->r;
    return c;
}

// apply lazy add to whole node (no pushing)
static inline void apply(Node* t, int add){
    t->v.first += add;
    t->lz += add;
}

// Pull up from children; null child means "implicit zeros" with full length
static inline void pull(Node* t){
    int leftLen  = t->m - t->s + 1;
    int rightLen = t->e - t->m;

    pll lv = t->l ? t->l->v : pll{0, leftLen};
    pll rv = t->r ? t->r->v : pll{0, rightLen};

    t->v = combine(lv, rv);
}

// PUSH lazy to children, cloning children at most once (only if lz != 0)
static inline void push(Node* t){
    if(t->lz == 0 || t->s == t->e) return;

    // ensure left child exists and is unique for this version
    if(!t->l) t->l = new Node(t->s, t->m);
    else      t->l = clone(t->l);
    apply(t->l, t->lz);

    // ensure right child exists and is unique for this version
    if(!t->r) t->r = new Node(t->m + 1, t->e);
    else      t->r = clone(t->r);
    apply(t->r, t->lz);

    t->lz = 0;
}

// Range add [L,R] by add, persistent: returns new node pointer
Node* update(Node* t, int L, int R, int add){
    if(!t) return nullptr; // shouldn't happen for your root, but safe

    Node* res = clone(t);

    if(L <= res->s && res->e <= R){
        apply(res, add);
        return res;
    }

    push(res);

    if(R <= res->m){
        if(!res->l) res->l = new Node(res->s, res->m); // create only when needed
        res->l = update(res->l, L, R, add);
    } else if(L > res->m){
        if(!res->r) res->r = new Node(res->m + 1, res->e);
        res->r = update(res->r, L, R, add);
    } else {
        if(!res->l) res->l = new Node(res->s, res->m);
        if(!res->r) res->r = new Node(res->m + 1, res->e);
        res->l = update(res->l, L, res->m, add);
        res->r = update(res->r, res->m + 1, R, add);
    }

    pull(res);
    return res;
}

/*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(0, m-s+1)), (r?r->v:mp(0, 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) 
		roots[k]=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++){
		//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) 
		roots[i]=update(roots[i-1], 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)
		roots[i]=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