Submission #980510

#	Time	Username	Problem	Language	Result	Execution time	Memory
980510		AlperenT_	Sličnost (COI23_slicnost)	C++17	67 / 100	1293 ms	524288 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 1e5 +10  , N = 1e5 +1  , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =1e9+7 ;
struct node{
    int mx, t, s , l , r ;
    node(){
        mx = s = l = r=  t =0 ;  
    }
};node nw ;
vector<node> seg ;
void mrg(int p){
    int l = seg[p].l , r= seg[p].r ;
    seg[p].s = seg[l].s + seg[r].s ;
    seg[p].mx = max(seg[l].mx , seg[l].s + seg[r].mx) ;
    if(seg[p].mx == seg[l].mx)seg[p].t += seg[l].t ;
    if(seg[p].mx == seg[l].s + seg[r].mx)seg[p].t += seg[r].t ;
}
int c =1 ,root[maxn] , p[maxn]  , pos[maxn]  , n , k , q ;

int  bui(int l = 1, int r =n-k+1){
    int mid = (l+r)/2 ;
    if(l == r){
        seg.pb(nw) ;
        seg[c].t = 1; 
        c++;
        return c-1;
    }
    int id = c ;c++;
    seg.pb(nw);
    seg[id].l = bui(l,mid);
    seg[id].r = bui(mid+1,r);
    mrg(id) ;
    return id ;
}
inline int ff(int l , int r , int x, int y){
    if((l <= x&& x <= r) || (l <= y && y <= r))return 1 ;
    return 0 ;
}
int upd(int x ,int w , int x2 , int w2 , int p , int l  ,int r){
    int id = c , mid = (l+r)/2 ; c++ ;
    seg.pb(nw);
    if(l == r){
        int su = seg[p].s ;
        if(x==l){
            su += w;
        }
        if(x2==l){
            su += w2 ;
        }
        seg[id].mx = seg[id].s = su;
        seg[id].t = 1; 
        return id ;
    }
    seg[id].l = seg[p].l ;
    seg[id].r = seg[p].r ; 
    if(ff(l , mid , x , x2))seg[id].l = upd(x,w,x2,w2,seg[p].l , l ,mid);
    if(ff(mid+1, r , x ,x2))seg[id].r = upd(x,w,x2,w2,seg[p].r ,mid+1,r);
    mrg(id) ;
    return id ;
}
map <int ,ll> mp ;
void add_(int x ,int y){
    mp[x] += y; 
}
void rem_(int x, int y){
    mp[x] -= y ;
    if(mp[x] == 0){
        mp.erase(x) ;
    }
}
void add(int x , int r){
    rem_(seg[root[r]].mx , seg[root[r]].t) ; 
    root[r]= upd((x+1 <= n-k+1 ? x+1 : max(1 ,x-k+1)) , (x+1 <= n-k+1 ? -1 : 0) , max(1 ,x-k+1), 1 , root[r] , 1 , n-k+1);
    add_(seg[root[r]].mx , seg[root[r]].t) ; 
}
void rem(int x , int r){
    rem_(seg[root[r]].mx , seg[root[r]].t) ; 
    root[r]= upd((x+1 <= n-k+1 ? x+1 : max(1 ,x-k+1)) , (x+1 <= n-k+1 ? 1 : 0) , max(1 ,x-k+1), -1 , root[r] , 1 , n-k+1);
    add_(seg[root[r]].mx , seg[root[r]].t) ; 
}
void cp(){
    cout << (*mp.rbegin()).F << " " << (*mp.rbegin()).S << "\n"; 
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0);
    seg.pb(nw) ;
    cin >> n >> k >> q ;
    rep(i ,1, n){
        cin >> p[i] ;
    } 
    rep(i ,1, n){
        int x; 
        cin >> x; 
        pos[x] = i;
    }
    rep(i ,1, n)p[i] = pos[p[i]] ;
    root[1] = bui();
    add_(0 , n-k+1);
    rep(i ,1 ,k){
        add(p[i] , 1) ;
    }
    rep(i ,2 , n-k+1){
        add_(seg[root[i-1]].mx , seg[root[i-1]].t) ; 
        root[i] = root[i-1] ;
        add(p[i+k-1], i) ;
        rem(p[i-1] , i) ;
    }
    cp();
    while(q--){
        int t ;
        cin>>t;
        if(t >= k){
            int f = t-k+1 ;
            add(p[t+1] , f) ;
            rem(p[t] , f); 
        }
        if(t+k <= n){
            add(p[t] , t+1);
            rem(p[t+1] , t+1);
        }
        swap(p[t] , p[t+1]); 
        cp(); 
    }
}

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