oj.uz

답안 #1014453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014453 2024-07-04T22:09:31 Z MarwenElarbi Sličnost (COI23_slicnost) C++17
0 / 100
 5 ms 9052 KB 
#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()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    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;
        long long 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;
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -