Submission #1014452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014452		MarwenElarbi	Sličnost (COI23_slicnost)	C++17	24 / 100	3070 ms	7032 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
const int MOD=1e9+7;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
pair<int,int> segtree[nax*4];
int lazy[nax*4];
int n,k,q;
void build(int pos,int l,int r){
    lazy[pos]=0;
    if(l==r){
        if(l<=n-k) segtree[pos]={0,1};
        else segtree[pos]={0,0};
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos].fi=max(segtree[pos*2+1].fi,segtree[pos*2+2].fi);
    if(segtree[pos*2+1].fi==segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
    else if(segtree[pos*2+1].fi>segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se;
    else segtree[pos].se=segtree[pos*2+2].se;
}
void propagate(int pos){
    if(lazy[pos]!=0){
        lazy[pos*2+1]+=lazy[pos];
        lazy[pos*2+2]+=lazy[pos];
        segtree[pos*2+1].fi+=lazy[pos];
        segtree[pos*2+2].fi+=lazy[pos];
    }
    lazy[pos]=0;
}
void update(int pos,int l,int r,int left,int right,int value){
    if(l>r||l>right||r<left) return;
    if(l>=left&&r<=right){
        segtree[pos].fi+=value;
        lazy[pos]+=value;
        return;
    }
    propagate(pos);
    int mid=(r+l)/2;
    update(pos*2+1,l,mid,left,right,value);
    update(pos*2+2,mid+1,r,left,right,value);
    segtree[pos].fi=max(segtree[pos*2+1].fi,segtree[pos*2+2].fi);
    if(segtree[pos*2+1].fi==segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
    else if(segtree[pos*2+1].fi>segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se;
    else segtree[pos].se=segtree[pos*2+2].se;
    return;
}
pair<int,int> query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return {0,0};
    if(l>=left&&r<=right){
        return segtree[pos];
    }
    propagate(pos);
    int mid=(r+l)/2;
    auto a=query(pos*2+1,l,mid,left,right);
    auto b=query(pos*2+2,mid+1,r,left,right);
    if(a.fi==b.fi) return {a.fi,b.se+a.se};
    else if(a.fi>b.fi) return a;
    else return b;
}
int main()
{
    optimise; 
    cin>>n>>k>>q;
    int a[n];
    int b[n];
    int pos[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin>>b[i];
        pos[b[i]-1]=i;
    }
    for (int i = 0; i < q+1; ++i)
    {
        if(i){
            int x;
            cin>>x;
            x--;
            swap(a[x],a[x+1]);
        }
        build(0,0,n-1);
        int res=0;
        int cnt=0;
        for (int i = 0; i < k; ++i)
        {
            update(0,0,n-1,max(pos[a[i]-1]-k+1,0),pos[a[i]-1],1);
            /*for (int i = 0; i < n; ++i)
            {
                cout << query(0,0,n-1,i,i).se <<" ";
            }cout <<endl;*/
        }
        //cout <<segtree[0].fi<<" "<<segtree[0].se<<endl;
        res=segtree[0].fi;
        cnt=segtree[0].se;
        for (int i = k; i < n; ++i)
        {
            update(0,0,n-1,max(pos[a[i-k]-1]-k+1,0),pos[a[i-k]-1],-1);
            
            update(0,0,n-1,max(pos[a[i]-1]-k+1,0),pos[a[i]-1],1);
            //cout <<a[i]<<" "<<max(pos[a[i]-1]-k+1,0)<<" "<<pos[a[i]-1]<<endl;
            //cout <<segtree[0].fi<<" "<<segtree[0].se<<endl;
            if(res<segtree[0].fi){
                cnt=segtree[0].se;
                res=segtree[0].fi;
            }else if(res==segtree[0].fi) cnt+=segtree[0].se;
        }
        cout <<res<<" "<<cnt<<endl;
    }
}

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