Submission #1256836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256836		nguyenhuythach	Exam (eJOI20_exam)	C++20	12 / 100	101 ms	16184 KiB

exam

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#define int long long
#define L LLONG_MAX
using namespace std;
long long n,t;
const int nmax=2e5+1;
int nxt1[nmax],nxt2[nmax],a[nmax],b[nmax],lazy[4*nmax];
pair<int,int> tree[4*nmax];
vector<pair<int,int>> save;
vector<pair<int,int>> order;

void build(int id,int l,int r)
{
    if(l==r)
    {
        tree[id].first=a[l];
        tree[id].second=b[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    tree[id].first=max(tree[id*2].first,tree[id*2+1].first);
    tree[id].second=min(tree[id*2].second,tree[id*2+1].second);
}

void down(int id,int l,int r)
{
    if(lazy[id]==0) return;
    tree[id].first=lazy[id];
    if(l!=r)
    {
        lazy[id*2]=lazy[id];
        lazy[id*2+1]=lazy[id];
    }
    lazy[id]=0;
}

void update(int id,int l,int r,int a,int b,int val)
{
    down(id,l,r);
    if(b<l||a>r) return;
    if(a<=l && r<=b)
    {
        lazy[id]=val;
        down(id,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,a,b,val);
    update(id*2+1,mid+1,r,a,b,val);
    tree[id].first=max(tree[id*2].first,tree[id*2+1].first);
}

int get(int id,int l,int r,int a)
{
    down(id,l,r);
    if(a<l || r<a) return 0;
    if(l==r) return tree[id].first;
    int mid=(l+r)/2;
    return get(id*2,l,mid,a)+get(id*2+1,mid+1,r,a);
}

int get1(int id,int l,int r,int a,int b)
{
    down(id,l,r);
    if(b<l||r<a) return 0;
    if(a<=l && r<=b) return tree[id].first;
    int mid=(l+r)/2;
    return max(get1(id*2,l,mid,a,b),get1(id*2+1,mid+1,r,a,b));
}

int get2(int id,int l,int r,int a,int b)
{
    down(id,l,r);
    if(b<l||r<a) return L;
    if(a<=l && r<=b) return tree[id].second;
    int mid=(l+r)/2;
    return min(get2(id*2,l,mid,a,b),get2(id*2+1,mid+1,r,a,b));
}

long long UPPER1(long long x)
{
    long long l=-1,r=save.size();
    while(l+1<r)
    {
        long long mid=(l+r)/2;
        if(save[mid].first>x) r=mid;
        else l=mid;
    }
    return r;
}

long long UPPER2(long long l,long long r,long long val)
{
    l--; r++;
    while(l+1<r)
    {
        long long mid=(l+r)/2;
        if(save[mid].second<=val) l=mid;
        else r=mid;
    }
    return r;
}

int getid1(int val,int id)
{
    int l=UPPER1(val-1),r=UPPER1(val);
    if(l==r) return -1;
    int p=UPPER2(l,r-1,id);
    if(p==r) return -1;
    else return save[p].second;
}

int getid2(int val,int id)
{
    int l=UPPER1(val-1),r=UPPER1(val);
    if(l==r) return -1;
    int p=UPPER2(l,r-1,id-1)-1;
    if(p<l) return -1;
    else return save[p].second;
}

void buildnxt1()
{
    for(int i=1;i<=n;i++) nxt1[i]=getid1(b[i],i);
}

void buildnxt2()
{
    for(int i=n;i>=1;i--) nxt2[i]=getid2(b[i],i);
}

void reset()
{
    for(int i=1;i<=4*n;i++)
    {
        tree[i].first=0;
        tree[i].second=L;
        lazy[i]=0;
    }
}

void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        save.push_back({a[i],i});
    }
    for(int i=1;i<=n;i++) 
    {
        cin >> b[i];
        order.push_back({b[i],i});
    }
    
    sort(save.begin(),save.end());
    sort(order.begin(),order.end());
    buildnxt1();
    buildnxt2();
    
    reset();
    build(1,1,n);
    int ans=0;
    for(int i=0;i<=n-1;i++)
    {
    	bool flag=false;
        //if(b[i-1]==b[i]) continue;
        int cur=get(1,1,n,order[i].second);
        if(cur>order[i].first) continue;
        if(cur==order[i].first) 
        {
        	ans++;
        	continue;
        }
        if(cur<order[i].first)
        {
            if(get1(1,1,n,order[i].second,nxt1[order[i].second])<=b[order[i].second] && get2(1,1,n,order[i].second,nxt1[order[i].second])>=b[order[i].second] && nxt1[order[i].second]!=-1)
            {
                update(1,1,n,order[i].second,nxt1[order[i].second],b[order[i].second]);
                flag=true;
            }
            if(get1(1,1,n,nxt2[order[i].second],order[i].second)<=b[order[i].second] && get2(1,1,n,nxt2[order[i].second],order[i].second)>=b[order[i].second] && nxt2[order[i].second]!=-1)
            {
                update(1,1,n,nxt2[order[i].second],order[i].second,b[order[i].second]);
                flag=true;
            }
            if(flag) ans++;
        }
    }
    cout << ans;
}

signed main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t=1;
    while(t--) 
    {
        solve();
        
        reset();
        save.clear();
        order.clear();
        for(int i=1;i<=n;i++)
        {
            nxt1[i]=0;
            nxt2[i]=0;
        }
    }
}

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