Submission #1256924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256924		nguyenhuythach	Exam (eJOI20_exam)	C++20	36 / 100	207 ms	58448 KiB

exam

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=5e5+1;
int n,crr=0;
int a[nmax],b[nmax];
map<int,int> mp;
set<int> s;
int mn[nmax][20]; //min
int mx[nmax][20]; //max
int L[nmax]; //log

int getmax(int x, int y)
{
    if(x>y) swap(x,y);
    int LOG=L[y-x+1];
    return max(mx[x][LOG],mx[y-(1<<LOG)+1][LOG]);
}

void build()
{
    for(int i=1;i<=n;i++) //base case
    {
        mn[i][0]=a[i];
        mx[i][0]=a[i];
    }
    for(int i=2;i<=n;i++) L[i]=L[i/2]+1; //build log arr
    for(int j=1;j<=L[n];j++)
    {
        for (int i = 1; i + (1<<j) - 1 <= n; ++i)
        {
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    }
}

struct BIT
{
    vector<int> tree;
    int n;
    
    BIT (int N)
    {
        n=N;
        tree.resize(n+69,0);
    }
    
    void update(int x,int val) {while(x<=n) { tree[x]=max(tree[x],val); x+=(x&-x);} }
    int get(int x) { int ans=0; while(x>0) {ans=max(ans,tree[x]); x-=(x&-x);} return ans; }
};

void input()
{
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) cin >> b[i];
    FOR(i,1,n) s.insert(a[i]);
    FORD(i,s) mp[i]=++crr;
    FOR(i,1,n)
    {
        a[i]=mp[a[i]];
        if(mp.count(b[i])) b[i]=mp[b[i]];
    }
}

namespace sub2
{
    bool check()
    {
        FOR(i,1,n) if(b[i]!=b[1]) return false;
        return (n>5000);
    }

    void solve()
    {
        int ans=0,start=1,flag=false;
        FOR(i,1,n)
        {
            if(!b[i]) continue;
            if(a[i]>b[1])
            {
                if(flag) ans+=i-start;
                start=i+1;
                flag=false;
            }
            if(a[i]==b[1]) flag=true;
        }
        if(flag) ans+=n-start+1;
        cout << ans;
    }
}

namespace sub4
{
    BIT bit(1e5+1);
    int pos[nmax];
    
    bool check()
    {
        return (n>5000);
    }
    
    void solve()
    {
        FOR(i,1,n) pos[a[i]]=i;
        FOR(i,1,n)
        {
            if(!b[i]) continue;
            if(getmax(pos[b[i]],i)>b[i]) continue;
            int pre=bit.get(pos[b[i]]);
            bit.update(pos[b[i]],pre+1);
        }
        cout << bit.get(crr);
    }
}

namespace sub1356
{
    BIT bit(5001);
    vector<int> pos[nmax];
    
    bool check()
    {
        return (n<=5000);
    }

    void solve()
    {
        FOR(i,1,n) pos[a[i]].push_back(i);
        FOR(i,1,n)
        {
            if(!b[i]) continue;
            REP(j,sz(pos[b[i]])-1,0)
            {
                if(getmax(j,i)>b[i]) continue;
                int id=pos[b[i]][j];
                int pre=bit.get(id);
                bit.update(id,pre+1);
            }
        }
        cout << bit.get(crr);
    }
}

void solve()
{
    build();
    if(sub2::check()) sub2::solve();
    else if(sub4::check()) sub4::solve();
    else if(sub1356::check()) sub1356::solve();
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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