oj.uz

Submission #830963

# Submission time Handle Problem Language Result Execution time Memory
830963 2023-08-19T13:44:33 Z vjudge1 Exam (eJOI20_exam) C++17
48 / 100
 104 ms 14796 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//turn on extra precision
//#pragma GCC target("fpmath=387")

using namespace std;
using namespace __gnu_pbds;

using str   = string;
using ll    = long long;
using pii   = pair <int,int>;
using pll   = pair <ll,ll>;
using vi    = vector <int>;
using vll   = vector <ll>;
using vpii  = vector <pii>;
using vpll  = vector <pll>;

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
    bool van = 1; os << '{';
    for(auto &i : v) { if(!van) os << ", "; os << i; van = 0; }
    os << '}'; return os;
}

template<class T, size_t sz>
ostream& operator<<(ostream&os, const array<T,sz> &arr) {
    bool fs = 1; os << '{';
    for(auto &i : arr) { if(!fs) os << ", "; os << i; fs = 0; }
    os << '}'; return os;
}

#define mp make_pair
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
#define all(x) x.begin(), x.end()
#define watch(x) cerr << (#x) << " is : " << (x) << newl

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
ll quickpow(ll num1, ll num2, const T MOD) {
    assert(num2 >= 0); ll ans = 1;
    for(; num2; num2>>=1, num1 = num1 * num1 % MOD) if(num2 & 1) ans = ans * num1 % MOD;
    return ans;
}
// end of Template

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    vector<int> a(n+1), b(n+1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];

    const auto sub2 = [&b, &n]() -> bool {
        for(int i = 2; i <= n; ++i) if(b[i] != b[i-1]) return false;
        return true;
    };

    const auto sub4 = [&a, &n]() -> bool {
        set<int> s;
        for(int i = 1; i <= n; ++i) s.emplace(a[i]);
        return s.size() == n;
    };

    if(sub2()) {
        bool hasb = false;
        int len = 0;

        int res = 0;
        for(int i = 1; i <= n; ++i) {
            if(a[i] > b[i]) {
                res += hasb * len;
                len = 0;
                hasb = false;
                continue;
            }

            ++len;
            if(a[i] == b[i]) hasb = true;
        }

        res += hasb * len;
        return cout << res << newl, 0;
    }

    if(sub4()) {
        map<int,int> pos;
        for(int i = 1; i <= n; ++i) pos[a[i]] = i;

        class sparseTable {
            private:
                vector<vector<int>> st;
                int n;
            public:
                sparseTable(vector<int> &v) : n(v.size() - 1) {
                    st.emplace_back(vector<int>(n+1));
                    for(int i = 1; i <= n; ++i) st[0][i] = v[i];

                    for(int i = 1; (1<<i) <= n; ++i) {
                        st.emplace_back(vector<int>(n+1));
                        for(int j = 1; j + (1<<i) - 1 <= n; ++j) {
                            st[i][j] = max(st[i-1][j], st[i-1][j+(1<<(i-1))]);
                        }
                    }
                }

                int getMin(int l, int r) {
                    int lv = __lg(r - l + 1);
                    return max(st[lv][l], st[lv][r-(1<<lv)+1]);
                }
        };

        class fenwick {
            private:
                vector<int> BIT;
                int n;
            public:
                fenwick(int n) : n(n) {
                    BIT.resize(n+1);
                }
                void update(int idx, int val) {
                    for(int i = idx; i <= n; i += i & -i) BIT[i] = max(BIT[i], val);
                    return;
                }
                int getMax(int idx) {
                    int res = 0;
                    for(int i = idx; i; i -= i & -i) res = max(res, BIT[i]);
                    return res;
                }
        };

        sparseTable sparse(a);
        fenwick BIT(n);

        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            if(!pos.count(b[i])) continue;
            if(sparse.getMin(min(i, pos[b[i]]), max(i, pos[b[i]])) > b[i]) continue;

            int res = 1 + BIT.getMax(pos[b[i]]);
            BIT.update(pos[b[i]], res);
            ans = max(ans, res);
        }

        return cout << ans << newl, 0;
    }

    cout << -1 << newl;

    return 0;
}

Compilation message

exam.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
exam.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
exam.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment(linker, "/stack:200000000")
      | 
exam.cpp: In lambda function:
exam.cpp:84:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         return s.size() == n;
      |                ~~~~~~~~~^~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 10 ms 980 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 15 ms 1108 KB Output is correct
6 Correct 9 ms 1108 KB Output is correct
7 Correct 9 ms 1108 KB Output is correct
8 Correct 16 ms 1108 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 4 ms 848 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 35 ms 6012 KB Output is correct
3 Correct 96 ms 14032 KB Output is correct
4 Correct 99 ms 14796 KB Output is correct
5 Correct 100 ms 14796 KB Output is correct
6 Correct 81 ms 14024 KB Output is correct
7 Correct 81 ms 14788 KB Output is correct
8 Correct 95 ms 14008 KB Output is correct
9 Correct 104 ms 13924 KB Output is correct
10 Correct 67 ms 13976 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -