Submission #1060325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060325		aymanrs	Sličnost (COI23_slicnost)	C++17	57 / 100	3076 ms	5484 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int nx = 4e5+100;
int st[nx], co[nx], lz[nx];
void cons(int i, int l, int r){
    st[i]=lz[i]=0;
    co[i] = r-l+1;
    if(l==r) return;
    int m = l+r>>1;
    cons(i<<1, l, m);cons(i<<1|1, m+1, r);
}
void upd(int i, int l, int r, int a, int b, int v){
    if(lz[i]){
        st[i] += lz[i];
        if(l!=r){
            lz[i<<1] += lz[i];
            lz[i<<1|1] += lz[i];
        }
        lz[i]=0;
    }
    if(b<l||r<a) return;
    if(a <= l && r <= b) {
        st[i] += v;
        if(l!=r){
            lz[i<<1] += v;
            lz[i<<1|1] += v;
        }
        return;
    }
    int m = l+r>>1;
    upd(i<<1, l, m, a, b, v);upd(i<<1|1, m+1, r, a, b, v);
    st[i] = max(st[i<<1], st[i<<1|1]);
    co[i] = 0;
    if(st[i<<1] == st[i]) co[i]=co[i<<1];
    if(st[i<<1|1] == st[i]) co[i]+=co[i<<1|1];
}
void ans(int n, int k, int a[], int b[]){
    cons(1, 0, n-1);
    for(int i = 0;i < k;i++) {
        upd(1, 0, n-1, max(0, b[a[i]]-k+1), min(n-k,b[a[i]]), 1);
    }
    int tans = st[1];long long c = co[1];
    for(int i = 1;i+k <= n;i++){
        upd(1, 0, n-1, max(0, b[a[i-1]]-k+1), min(n-k,b[a[i-1]]), -1);
        upd(1, 0, n-1, max(0, b[a[i+k-1]]-k+1), min(n-k,b[a[i+k-1]]), 1);
        if(st[1] > tans){
            tans = st[1];
            c = co[1];
        } else if(st[1] == tans) c += co[1];
    }
    cout << tans << ' ' << c << '\n';
}
void solve(){
    int n, k ,q;cin >> n >> k >> q;
    int a[n],b[n+1];
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int i = 0;i < n;i++) {
        int th;cin >> th;
        b[th] = i;
    }
    ans(n, k, a, b);
    while(q--){
        int p;cin >> p;
        p--;
        swap(a[p],a[p+1]);
        ans(n,k,a,b);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void cons(int, int, int)':
Main.cpp:11:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     int m = l+r>>1;
      |             ~^~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int m = l+r>>1;
      |             ~^~

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