oj.uz

Submission #1104366

# Submission time Handle Problem Language Result Execution time Memory
1104366 2024-10-23T14:04:27 Z TrinhKhanhDung Exam (eJOI20_exam) C++14
100 / 100
 76 ms 103372 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(), v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define INF (ll)1e9
#define oo (ll)1e18
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 2e5 + 10;

int N;
int A[MAX], B[MAX], lef[MAX], rig[MAX];

void input(){
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> A[i];
    for(int i = 1; i <= N; i++) cin >> B[i];
}

void compress(){
    vector<int> tmp;
    for(int i = 1; i <= N; i++) tmp.push_back(A[i]);
    for(int i = 1; i <= N; i++) tmp.push_back(B[i]);
    cps(tmp);
    for(int i = 1; i <= N; i++) A[i] = lower_bound(ALL(tmp), A[i]) - tmp.begin();
    for(int i = 1; i <= N; i++) B[i] = lower_bound(ALL(tmp), B[i]) - tmp.begin();
}

void setup(){
    for(int i = 1; i <= N; i++){
        lef[i] = i - 1;
        while(lef[i] > 0 && A[i] >= A[lef[i]]) lef[i] = lef[lef[i]];
    }
    for(int i = N; i >= 1; i--){
        rig[i] = i + 1;
        while(rig[i] <= N && A[i] >= A[rig[i]]) rig[i] = rig[rig[i]];
    }
}

namespace subtask2{
    bool check(){
        for(int i = 1; i <= N; i++){
            if(B[i] != B[1]) return false;
        }
        return true;
    }

    int D[MAX];

    void solve(){
        for(int i = 1; i <= N; i++){
            if(A[i] == B[i]){
                D[lef[i] + 1]++;
                D[rig[i]]--;
            }
        }
        int ans = 0;
        for(int i = 1; i <= N; i++){
            D[i] += D[i - 1];
            ans += (D[i] > 0);
        }

        cout << ans << '\n';
    }
}

namespace subtask3{
    bool check(){
        for(int i = 2; i <= N; i++){
            if(A[i] <= A[i - 1]) return false;
        }
        return true;
    }

    const int MAX = 5003;

    int f[MAX][MAX];
    //f[i][j]: ap dung nhung thay doi tu A[1] -> A[i] cho nhung thang tu 1 -> j

    void solve(){
        int ans = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= i; j++){
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if(A[i] == B[j]){
                    maximize(f[i][j], f[i][j - 1] + 1);
                }
                maximize(ans, f[i][j]);
            }
        }

        cout << ans << '\n';
    }
}

namespace seg{
    int it[MAX * 4];
    int n;

    void init(int _n = 0){
        n = _n;
        memset(it, 0, n * 4 * sizeof(int));
    }

    void upd(int p, int c){
        int i = 1, l = 1, r = n;
        while(l < r){
            int m = (l + r) >> 1;
            if(p <= m){
                i = i * 2;
                r = m;
            }
            else{
                i = i * 2 + 1;
                l = m + 1;
            }
        }
        maximize(it[i], c);
        while(i > 1){
            i >>= 1;
            it[i] = max(it[i * 2], it[i * 2 + 1]);
        }
    }

    int get(int u, int v, int i = 1, int l = 1, int r = n){
        if(r < u || v < l) return 0;
        if(u <= l && r <= v) return it[i];
        int m = (l + r) >> 1;
        return max(get(u, v, i * 2, l, m), get(u, v, i * 2 + 1, m + 1, r));
    }
}

namespace subtask4{
    bool check(){
        vector<int> tmp;
        for(int i = 1; i <= N; i++) tmp.push_back(A[i]);
        cps(tmp);
        return sz(tmp) == N;
    }

    int pos[MAX];

    void solve(){
        seg::init(N);

        for(int i = 1; i <= N; i++){
            pos[A[i]] = i;
        }

        for(int i = 1; i <= N; i++){
            int p = pos[B[i]];
            if(p == 0) continue;
            if(lef[p] < i && i < rig[p]){
                seg::upd(p, seg::get(1, p) + 1);
            }
        }

        cout << seg::it[1] << '\n';
    }
}

namespace subtask6{
    const int MAX = 5003;

    int f[MAX][MAX];
    //f[i][j]: ap dung nhung thay doi tu A[1] -> A[i] cho nhung thang tu 1 -> j

    void solve(){
        int ans = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if(A[i] == B[j] && lef[i] < j && j < rig[i]){
                    maximize(f[i][j], f[i][j - 1] + 1);
                }
                maximize(ans, f[i][j]);
            }
        }

        cout << ans << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("creature.inp", "r", stdin);
//    freopen("creature.out", "w", stdout);

    input();
    compress();
    setup();

    if(subtask2::check()) return subtask2::solve(), 0;
    if(subtask3::check()) return subtask3::solve(), 0;
    if(subtask4::check()) return subtask4::solve(), 0;
    return subtask6::solve(), 0;

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 6 ms 4660 KB Output is correct
3 Correct 24 ms 4504 KB Output is correct
4 Correct 17 ms 4736 KB Output is correct
5 Correct 42 ms 4776 KB Output is correct
6 Correct 16 ms 4940 KB Output is correct
7 Correct 22 ms 4540 KB Output is correct
8 Correct 40 ms 6676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 4 ms 6992 KB Output is correct
3 Correct 12 ms 24656 KB Output is correct
4 Correct 39 ms 76616 KB Output is correct
5 Correct 49 ms 78508 KB Output is correct
6 Correct 37 ms 78652 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8776 KB Output is correct
2 Correct 24 ms 9736 KB Output is correct
3 Correct 52 ms 9396 KB Output is correct
4 Correct 55 ms 9396 KB Output is correct
5 Correct 64 ms 11548 KB Output is correct
6 Correct 76 ms 9396 KB Output is correct
7 Correct 69 ms 11444 KB Output is correct
8 Correct 66 ms 10668 KB Output is correct
9 Correct 65 ms 10676 KB Output is correct
10 Correct 50 ms 10696 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 5456 KB Output is correct
11 Correct 3 ms 5456 KB Output is correct
12 Correct 2 ms 5456 KB Output is correct
13 Correct 2 ms 5456 KB Output is correct
14 Correct 2 ms 5456 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 4 ms 6992 KB Output is correct
9 Correct 12 ms 24656 KB Output is correct
10 Correct 39 ms 76616 KB Output is correct
11 Correct 49 ms 78508 KB Output is correct
12 Correct 37 ms 78652 KB Output is correct
13 Correct 1 ms 4432 KB Output is correct
14 Correct 1 ms 4688 KB Output is correct
15 Correct 2 ms 4944 KB Output is correct
16 Correct 2 ms 5456 KB Output is correct
17 Correct 3 ms 5456 KB Output is correct
18 Correct 2 ms 5456 KB Output is correct
19 Correct 2 ms 5456 KB Output is correct
20 Correct 2 ms 5456 KB Output is correct
21 Correct 2 ms 5456 KB Output is correct
22 Correct 7 ms 15184 KB Output is correct
23 Correct 2 ms 4688 KB Output is correct
24 Correct 46 ms 103256 KB Output is correct
25 Correct 45 ms 103372 KB Output is correct
26 Correct 39 ms 103328 KB Output is correct
27 Correct 47 ms 103168 KB Output is correct
28 Correct 41 ms 103240 KB Output is correct
29 Correct 44 ms 103256 KB Output is correct
30 Correct 49 ms 103240 KB Output is correct
31 Correct 45 ms 103240 KB Output is correct
32 Correct 40 ms 103248 KB Output is correct