제출 #1320065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320065		erering	Exam (eJOI20_exam)	C++20	0 / 100	5 ms	1684 KiB

exam

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=1e5+5,MAXA=1e6+5,inf=1e9,MOD=1e9+7;
int n,a[N],b[N],srt[N],seg[N*4],offset=1,lft[N],rt[N];
void update(int idx,bool flag){
   idx+=offset;
   seg[idx]=flag;
   idx/=2;
   while(idx>0){
       seg[idx]=seg[idx*2]+seg[idx*2+1];
       idx/=2;
   }
}
int query(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg[node];
    if(lo>qhi || hi<qlo)return 0;
    int mid=(lo+hi)/2;
    return query(node*2,qlo,qhi,lo,mid)+query(node*2+1,qlo,qhi,mid+1,hi);
}
vector<int> posb[N],posa[N];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    while(offset<=n)offset*=2;
    deque<pair<int,int>> dq={{inf,0}};
    set<int> comp;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        comp.insert(a[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        comp.insert(b[i]);
    }
    map<int,int> id;
    int cnt=1;
    for(auto i:comp)id[i]=cnt++;
    for(int i=1;i<=n;i++){
        a[i]=id[a[i]];
        while(a[i]>=dq.back().first)dq.pop_back();
        lft[i]=dq.back().second;
        dq.pb({a[i],i});
        posa[a[i]].pb(i);
        srt[i]=a[i];
    }
    dq={{inf,n+1}};
    for(int i=n;i>0;i--){
        while(a[i]>=dq.front().first)dq.pop_front();
        rt[i]=dq.front().second;
        dq.push_front({a[i],i});
    }
    set<int> correct;
    int ans=0;
    for(int i=1;i<=n;i++){
        b[i]=id[b[i]];
        if(a[i]==b[i]){
            ans++;
            update(i,1);
            correct.insert(i);
        }
        posb[b[i]].pb(i);
    }
    sort(srt+1,srt+n+1);
    for(int i=1;i<=n;i++){
        int el=srt[i],pos=posa[srt[i]][0],inc=0;
        pair<int,int> mx={0,pos};
        for(int j=0;j<posb[el].size();j++){
            int cur=posb[el][j];
            if(cur>=rt[el])break;
            if(cur>pos){
                inc++;
                mx=max(mx,{inc-query(1,pos+1,cur,0,offset-1),cur});
            }
        }
        if(mx.first){
            auto it=correct.upper_bound(pos);
            while(it!=correct.end() && *it<=mx.second){
                update(*it,0);
                it=correct.erase(it);
            }
            for(int j=0;j<posb[el].size();j++){
                int cur=posb[el][j];
                if(cur>mx.second)break;
                if(cur>pos){
                    correct.insert(cur);
                    update(cur,1);
                }
            }
            ans+=mx.first;
        }
        mx={0,pos}; inc=0;
        for(int j=posb[el].size()-1;j>=0;j--){
            int cur=posb[el][j];
            if(cur<=lft[el])break;
            if(cur<pos){
                inc++;
                mx=max(mx,{inc-query(1,cur,pos-1,0,offset-1),cur});
            }
        }
        if(mx.first){
            auto it=correct.lower_bound(mx.second);
            while(it!=correct.end() && *it<pos){
                update(*it,0);
                it=correct.erase(it);
            }
            for(int j=posb[el].size()-1;j>=0;j--){
                int cur=posb[el][j];
                if(cur<mx.second)break;
                if(cur<pos){
                    correct.insert(cur);
                    update(cur,1);
                }
            }
            ans+=mx.first;
        }
    }
    cout<<ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22