Submission #1256943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256943		nguyenhuythach	Exam (eJOI20_exam)	C++20	88 / 100	1097 ms	52908 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 L[nmax]; // log floor

// sparse table stored dynamically to avoid huge static allocation
vector<vector<int>> mn; // not really used but keep for parity
vector<vector<int>> mx;

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

void build()
{
    // compute logs
    L[1] = 0;
    for(int i=2;i<=n;i++) L[i]=L[i/2]+1;

    int maxLog = L[n];
    // allocate sparse table: indices 1..n, logs 0..maxLog
    mx.assign(n+1, vector<int>(maxLog+1, 0));
    mn.assign(n+1, vector<int>(maxLog+1, 0)); // kept if needed later

    for(int i=1;i<=n;i++) // base case
    {
        mn[i][0]=a[i];
        mx[i][0]=a[i];
    }
    for(int j=1;j<=maxLog;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=0)
    {
        n=N;
        tree.assign(n+5,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]);
    // map values in increasing order (1-based ranks)
    FORD(val, s) mp[val]=++crr;
    FOR(i,1,n)
    {
        a[i]=mp[a[i]];
        if(mp.count(b[i])) b[i]=mp[b[i]];
        else b[i]=0;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();

    // allocate pos according to compressed size
    vector<vector<int>> pos(crr+1);
    FOR(i,1,n) pos[a[i]].push_back(i);

    build();

    BIT bit(n); // sized by n
    vector<pair<int,int>> ops;
    // collect ops in same order as original logic: for each i in B, push valid positions of that value (right->left)
    FOR(i,1,n)
    {
        if(!b[i]) continue;
        for(int j = (int)pos[b[i]].size()-1; j>=0; --j)
        {
            int id = pos[b[i]][j];
            if(getmax(id,i) > b[i]) continue;
            int pre = bit.get(id);
            bit.update(id, pre+1);
        }
    }
    cout << bit.get(n) << '\n';
    return 0;
}

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