oj.uz

Submission #806217

# Submission time Handle Problem Language Result Execution time Memory
806217 2023-08-04T05:18:27 Z josiftepe Exam (eJOI20_exam) C++14
55 / 100
 251 ms 201416 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int INF = 2e9;
int n;
int a[maxn], b[maxn];
int L[maxn], R[maxn];
int segment_tree[3 * maxn];
void solve_subtask2() {
    int x = b[0];
    int res = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == x) {
            res++;
            int j = i - 1;
            while(j >= 0 and a[j] <= x) {
                j--;
                res++;
            }
            j = i + 1;
            while(j < n and a[j] <= x) {
                res++;
                j++;
            }
            i = j - 1;
        }
    }
    cout << res << endl;
}
int dp[5005][5005];
int rec(int i, int j) {
    if(i < 0 or j < 0) {
        return 0;
    }
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    int res = 0;
    if(a[i] == b[j] and L[i] < j and R[i] > j) {
        res = max(res, rec(i, j - 1) + 1);
    }
    res = max(res, rec(i - 1, j));
    res = max(res, rec(i, j - 1));
    return dp[i][j] = res;
}
void build_tree(int L, int R, int node) {
    if(L == R) {
        segment_tree[node] = 0;
        return;
    }
    int middle = (L + R) / 2;
    build_tree(L, middle, 2 * node);
    build_tree(middle + 1, R, 2 * node + 1);
    segment_tree[node] = max(segment_tree[2 * node], segment_tree[2 * node + 1]);
}
int query(int i, int j, int L, int R, int node) {
    // L  R i L R j L R
    if(i <= L and R <= j) {
        return segment_tree[node];
    }
    if(R < i or j < L) {
        return 0;
    }
    int middle = (L + R) / 2;
    return max(query(i, j, L, middle, 2 * node), query(i, j, middle + 1, R, 2 * node + 1));
}
void update(int idx, int new_value, int L, int R, int node) {
    if(L == R) {
        segment_tree[node] = new_value;
        return;
    }
    int middle = (L + R) / 2;
    if(idx <= middle) {
        update(idx, new_value, L, middle, 2 * node);
    }
    else {
        update(idx, new_value, middle + 1, R, 2 * node + 1);
    }
    segment_tree[node] = max(segment_tree[2 * node], segment_tree[2 * node + 1]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    set<int> st;
    vector<int> t(n + 1);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        t[i + 1] = a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> b[i];
        st.insert(b[i]);
    }
    t[0] = INF;
    t[n + 1] = INF;
    stack<int> s;
    s.push(0);
    for(int i = 1; i <= n; i++) {
        while(t[s.top()] <= t[i]) {
            s.pop();
        }
        L[i - 1] = s.top() - 1;
        s.push(i);
    }
    while(!s.empty()) {
        s.pop();
    }
    s.push(n + 1);
    for(int i = n; i > 0; i--) {
        while(t[s.top()] <= t[i]) {
            s.pop();
        }
        R[i - 1] = s.top() - 1;
        s.push(i);
    }
    
    if((int) st.size() == 1) {
        solve_subtask2();
        return 0;
    }
    else if(n <= 5005){
        memset(dp, -1, sizeof dp);
        cout << rec(n - 1, n - 1) << endl;
    }
    else {
        build_tree(0, n, 1);
        map<int, int> m;
        for(int i = 0; i < n; i++) {
            m[a[i]] = i;
        }
        
        for(int i = 0; i < n; i++) {
            map<int, int>::iterator it = m.find(b[i]);
            if(it != m.end()) {
                int idx = it->second;
                if(L[idx] < i and i < R[idx]) {
                    int dp = query(0, idx, 0, n, 1);
                    update(idx, dp + 1, 0, n, 1);
                }
            }
        }
        cout << query(0, n, 0, n, 1) << endl;
    }
    
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 98388 KB Output is correct
2 Correct 29 ms 98380 KB Output is correct
3 Correct 29 ms 98388 KB Output is correct
4 Correct 34 ms 98328 KB Output is correct
5 Correct 31 ms 98388 KB Output is correct
6 Correct 32 ms 98356 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 1108 KB Output is correct
3 Correct 14 ms 3432 KB Output is correct
4 Correct 14 ms 2644 KB Output is correct
5 Correct 26 ms 4192 KB Output is correct
6 Correct 11 ms 2644 KB Output is correct
7 Correct 13 ms 2772 KB Output is correct
8 Correct 20 ms 4164 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 98276 KB Output is correct
2 Correct 34 ms 98432 KB Output is correct
3 Correct 52 ms 98748 KB Output is correct
4 Correct 177 ms 99400 KB Output is correct
5 Correct 157 ms 99464 KB Output is correct
6 Correct 160 ms 99540 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 201416 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 98388 KB Output is correct
2 Correct 29 ms 98380 KB Output is correct
3 Correct 29 ms 98388 KB Output is correct
4 Correct 34 ms 98328 KB Output is correct
5 Correct 31 ms 98388 KB Output is correct
6 Correct 32 ms 98356 KB Output is correct
7 Correct 34 ms 98380 KB Output is correct
8 Correct 31 ms 98276 KB Output is correct
9 Correct 31 ms 98360 KB Output is correct
10 Correct 32 ms 98304 KB Output is correct
11 Correct 41 ms 98348 KB Output is correct
12 Correct 31 ms 98380 KB Output is correct
13 Correct 31 ms 98352 KB Output is correct
14 Correct 33 ms 98380 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 98388 KB Output is correct
2 Correct 29 ms 98380 KB Output is correct
3 Correct 29 ms 98388 KB Output is correct
4 Correct 34 ms 98328 KB Output is correct
5 Correct 31 ms 98388 KB Output is correct
6 Correct 32 ms 98356 KB Output is correct
7 Correct 31 ms 98276 KB Output is correct
8 Correct 34 ms 98432 KB Output is correct
9 Correct 52 ms 98748 KB Output is correct
10 Correct 177 ms 99400 KB Output is correct
11 Correct 157 ms 99464 KB Output is correct
12 Correct 160 ms 99540 KB Output is correct
13 Correct 34 ms 98380 KB Output is correct
14 Correct 31 ms 98276 KB Output is correct
15 Correct 31 ms 98360 KB Output is correct
16 Correct 32 ms 98304 KB Output is correct
17 Correct 41 ms 98348 KB Output is correct
18 Correct 31 ms 98380 KB Output is correct
19 Correct 31 ms 98352 KB Output is correct
20 Correct 33 ms 98380 KB Output is correct
21 Runtime error 110 ms 199328 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -