Submission #1191212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191212		The_Samurai	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	435 ms	61932 KiB

Main

// I stand with PALESTINE



//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define int long long
#define ff first
#define ss second
#define sz(a) (int) (a).size()
//template<class T, class C = null_type> using ordered_tree = tree<T, C, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long double ld;

namespace io {

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const pair<F, S> &p) { return os << p.ff << " " << p.ss; }

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const map<F, S> &mp) {
        for (auto it: mp) { os << it << endl; }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const vector<F> &v) {
        bool space = false;
        for (F x: v) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const deque<F> &d) {
        bool space = false;
        for (F x: d) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const set<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const multiset<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x << x;
        }
        return os;
    }

    template<typename F, typename S>
    istream &operator>>(istream &is, pair<F, S> &p) { return is >> p.ff >> p.ss; }

    template<typename F>
    istream &operator>>(istream &is, vector<F> &v) {
        for (F &x: v) { is >> x; }
        return is;
    }

    long long fastread() {
        char c;
        long long d = 1, x = 0;
        do c = getchar(); while (c == ' ' || c == '\n');
        if (c == '-') c = getchar(), d = -1;
        while (isdigit(c)) {
            x = x * 10 + c - '0';
            c = getchar();
        }
        return d * x;
    }

    static bool sep = false;

    using std::to_string;

    string to_string(bool x) {
        return (x ? "true" : "false");
    }

    string to_string(const string &s) { return "\"" + s + "\""; }

    string to_string(const char *s) { return "\"" + string(s) + "\""; }

    string to_string(const char &c) {
        string s;
        s += c;
        return "\'" + s + "\'";
    }

    template<typename Type>
    string to_string(vector<Type>);

    template<typename F, typename S>
    string to_string(pair<F, S>);

    template<typename Collection>
    string to_string(Collection);

    template<typename F, typename S>
    string to_string(pair<F, S> p) { return "{" + to_string(p.ff) + ", " + to_string(p.ss) + "}"; }

    template<typename Type>
    string to_string(vector<Type> v) {
        bool sep = false;
        string s = "[";
        for (Type x: v) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "]";
        return s;
    }

    template<typename Collection>
    string to_string(Collection collection) {
        bool sep = false;
        string s = "{";
        for (auto x: collection) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "}";
        return s;
    }

    void print() {
        cout << endl;
        sep = false;
    }

    template<typename F, typename... Other>
    void print(F ff, Other... other) {
        if (sep) cout << " | ";
        sep = true;
        cout << to_string(ff);
        print(other...);
    }

}
using namespace io;

namespace utils {

    template<typename F, typename S>
    inline void maxs(F &a, S b) { a = a > b ? a : b; }

    template<typename F, typename S>
    inline void mins(F &a, S b) { a = a < b ? a : b; }

    template<typename F, typename S>
    long long max(F a, S b) { return a > b ? a : b; }

    template<typename F, typename S>
    long long min(F a, S b) { return a < b ? a : b; }

    constexpr long long operator "" _E(unsigned long long n) {
        long long p = 1, a = 10;
        for (int i = 0; i < n; i++) p *= a;
        return p;
    }

    random_device rd;
    mt19937 mt(rd());

    template<typename T>
    T rand(T l, T r) {
        uniform_int_distribution<T> dist(l, r);
        return dist(mt);
    };

}
using namespace utils;


#ifdef sunnatov
#define print(...) cout << "[" << #__VA_ARGS__ << "]: "; io::print( __VA_ARGS__ );
#else
#define print( ... ) 42
#endif

const int mod = 9_E + 7;
const double EPS = 1e-7;
long long doxuya = 18_E + 10;
int INF = 9_E + 10;
const char nl = '\n';

int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

/*

*/

struct SegmentTree {
    int n;
    std::vector<int> sum;

    void init(int size) {
        n = 1;
        while (n < size) n *= 2;
        sum.assign(n * 2, 0);
    }

    int merge(int a, int b) {
        return a + b;
    }

    void upd(int p, int value, bool add) {
        p += n;
        if (add) sum[p] += value;
        else sum[p] = value;
        for (; p > 1; p >>= 1) sum[p >> 1] = merge(sum[p], sum[p ^ 1]);
    }

    int select(int p, int l, int r, int k) {
        if (r - l == 1) {
            return l;
        } else {
            int m = (l + r) / 2;
            if (k <= sum[2 * p]) {
                return select(2 * p, l, m, k);
            } else {
                return select(2 * p + 1, m, r, k - sum[2 * p]);
            }
        }
    }
    int select(int k) {
        return select(1, 0, n, k);
    }

    int get(int l, int r) {  // sum on interval [l, r]
        if (l > r) return 0;
        int res = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = merge(res, sum[l++]);
            if (r & 1) res = merge(res, sum[--r]);
        }
        return res;
    }
};

void solution(istream &cin, ostream &cout, const int &test_case) {
    int n, q;
    cin >> n >> q;
    vector<vector<pair<int, int>>> queries(n + 2);
    vector<int> a(n + 2, INF), ans(q);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) {
        int t, pos;
        cin >> t >> pos;
        if (t == 0) ans[i] = a[pos];
        else queries[min(n + 1, t)].emplace_back(pos, i);
    }

    stack<int> s;
    vector<int> right(n + 1), left(n + 1), pos(n + 1);
    for (int i = n; i > 0; i--) {
        while (!s.empty() and a[i] > a[s.top()]) s.pop();
        right[i] = s.empty() ? n + 1 : s.top();
        pos[a[i]] = i;
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 1; i <= n; i++) {
        while (!s.empty() and a[i] > a[s.top()]) s.pop();
        left[i] = s.empty() ? 0 : s.top();
        s.push(i);
    }

    set<int> st;
    SegmentTree sg; sg.init(n + 1);
    vector<int> fixed(n + 1, -1);
    int last = -1;
    for (int i = 1; i <= n; i++) {
        if (i <= n / 2 and left[i] == 0 or i > n / 2 and left[i] <= n / 2) {
            st.insert(a[i]);
            last = a[i];
        }
        sg.upd(last, 1, true);
    }
    int z = n;
    for (int t = 1; t <= n + 1; t++) {
        while (sg.get(0, *st.rbegin() - 1) + 1 > n / 2) {
            int x = *st.rbegin();
            int len = sg.get(x, x);
            for (int i = z - len + 1, j = 0; i <= z; i++, j++) {
                fixed[i] = a[pos[x] + j];
            }
            sg.upd(x, 0, false);
            st.erase(x);
            z -= len;     
        }

        for (auto [p, i]: queries[t]) {
            if (fixed[p] != -1) {
                ans[i] = fixed[p];
                continue;
            }
            int x = sg.select(p);
            ans[i] = a[pos[x] + (p - sg.get(0, x - 1) - 1)];
        }

        if (sg.get(0, n) <= n / 2) continue;
        int x = *st.rbegin();
        int start = pos[x] + (n / 2 - sg.get(0, x - 1));
        int end = pos[x] + sg.get(x, x) - 1;
        for (int i = start; i <= end; ) {
            int r = min(end, right[i] - 1);
            sg.upd(x, -(r - i + 1), true);
            sg.upd(a[i], r - i + 1, true);
            st.insert(a[i]);
            i = r + 1;
        }
    }
    for (int x: ans) cout << x << nl;
}

int32_t main() {
    clock_t startTime = clock();
    cin.tie(0)->sync_with_stdio(false);
    srand(time(0));

    std::istream &in(std::cin);
    std::ostream &out(std::cout);

    int32_t queries = 1;

#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> queries;
#else
    // cin >> queries;
#endif

    for (int32_t test_case = 1; test_case <= queries; test_case++) {
        print(test_case);
        solution(cin, cout, test_case);
        cout << nl;
    }

#ifdef sunnatov
    cout << "Time: " << (int) ((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return EXIT_SUCCESS;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25