oj.uz

Submission #839469

# Submission time Handle Problem Language Result Execution time Memory
839469 2023-08-30T05:42:03 Z abysmal Abracadabra (CEOI22_abracadabra) C++14
100 / 100
 500 ms 49568 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 100;
const int64_t mINF = (int64_t) 1e9 + 100;
const int64_t MOD = 1e9 + 19972207;
const int64_t MOD2 = 998244353;
const int nbit = 31;
const int ndig = 10;
const int nchar = 26;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};

struct Query
{
    int t;
    int k;
    int id;

    Query(int t_, int k_, int id_) : t(t_), k(k_), id(id_) {}

    bool operator < (const Query& o) const
    {
        if(t != o.t) return t < o.t;
        if(k != o.k) return k < o.k;
        return id < o.id;
    }
};

struct Thing
{
    int val;
    int l;
    int r;

    Thing(int val_, int l_, int r_) : val(val_), l(l_), r(r_) {}

    bool operator < (const Thing& o) const
    {
        if(val == o.val)
        {
            if(l == o.l) return r < o.r;
            return l < o.l;
        }
        return val < o.val;
    }
};

struct Solution
{
    int n;
    int m;
    int q;
    int sz;
    set<Thing> st;
    vector<int> a;
    vector<int> nx;
    vector<Query> v;
    vector<int> tree;
    vector<int> ans;
    Solution() {}

    void solve()
    {
        cin >> n >> q;
        a.resize(n, 0);
        nx.resize(n, n - 1);
        vector<int> pos(n, -1);
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            a[i]--;
            pos[a[i]] = i;
        }

        for(int i = 0; i < q; i++)
        {
            int t;
            int k;
            cin >> t >> k;
            t = min(t, n);
            v.push_back(Query(t, k, i));
        }
        sort(v.begin(), v.end());

        m = n;
        sz = 0;
        while(__builtin_popcount(m) != 1) m++;
        tree.resize(2 * m, 0);
        stack<int> s;
        for(int i = 0; i < n; i++)
        {
            while(!s.empty() && a[s.top()] < a[i])
            {
                nx[s.top()] = i - 1;
                s.pop();
            }

            s.push(i);
        }

        int j = 0;
        ans.resize(q, -1);
        addBlocks(0, n - 1);
        for(int i = 0; i <= n; i++)
        {
            while(j < q && v[j].t == i)
            {
                int p = n;
                int x = getAns(1, 0, m - 1, v[j].k, p);
                ans[v[j].id] = a[pos[x] + v[j].k - p - 1] + 1;
                j++;
            }

            deleteRight();
            if(sz > n / 2)
            {
                Thing mid = (*prev(st.end()));
                st.erase(mid);

                int x = mid.r - (sz - n / 2);
                update(mid.val, x - mid.l + 1);
                st.insert(Thing(mid.val, mid.l, x));
                addBlocks(x + 1, mid.r);
                sz -= (mid.r - mid.l + 1);
                sz += (x - mid.l + 1);
            }
        }

        for(int i = 0; i < q; i++)
        {
            cout << ans[i] << "\n";
        }
    }

    void deleteRight()
    {
        set<Thing>::iterator it = prev(st.end());
        do
        {
            int len = (*it).r - (*it).l + 1;
            if(sz - len < n / 2) break;

            st.erase(it);
            it = prev(st.end());
            sz -= len;
        } while(it != st.begin());
    }

    void addBlocks(int l, int r)
    {
        while(l <= r)
        {
            int e = min(nx[l], r);
            int len = e - l + 1;
            sz += len;
            st.insert(Thing(a[l], l, e));

            update(a[l], len);
            l = nx[l] + 1;
        }
    }

    int getAns(int node, int nleft, int nright, int id, int& p)
    {
        if(nleft == nright)
        {
            p -= tree[node];
            return nleft;
        }

        int mid = nleft + (nright - nleft) / 2;
        if(p - tree[node * 2 + 1] >= id)
        {
            p -= tree[node * 2 + 1];
            return getAns(node * 2, nleft, mid, id, p);
        }
        return getAns(node * 2 + 1, mid + 1, nright, id, p);
    }

    void update(int id, int val)
    {
        tree[m + id] = val;
        for(int i = (m + id) / 2; i >= 1; i /= 2)
        {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;
        return res;
    }

    int modsub(int t1, int t2)
    {
        int res = t1 - t2;
        if(res < 0) res += MOD;
        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int Abs(int tmp)
    {
        if(tmp < 0) return -tmp;
        return tmp;
    }

    int MASK(int j)
    {
        return (1 << j);
    }

    bool BIT(int tmp, int j)
    {
        return (tmp & MASK(j));
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 19868 KB Output is correct
2 Correct 304 ms 20904 KB Output is correct
3 Correct 290 ms 20100 KB Output is correct
4 Correct 267 ms 19976 KB Output is correct
5 Correct 281 ms 20716 KB Output is correct
6 Correct 274 ms 19992 KB Output is correct
7 Correct 291 ms 20876 KB Output is correct
8 Correct 270 ms 20256 KB Output is correct
9 Correct 274 ms 19912 KB Output is correct
10 Correct 276 ms 20272 KB Output is correct
11 Correct 273 ms 20216 KB Output is correct
12 Correct 266 ms 19976 KB Output is correct
13 Correct 276 ms 20280 KB Output is correct
14 Correct 277 ms 20496 KB Output is correct
15 Correct 277 ms 20756 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 267 ms 20236 KB Output is correct
18 Correct 269 ms 20096 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 33460 KB Output is correct
2 Correct 339 ms 49568 KB Output is correct
3 Correct 318 ms 38880 KB Output is correct
4 Correct 269 ms 35744 KB Output is correct
5 Correct 315 ms 36756 KB Output is correct
6 Correct 275 ms 35368 KB Output is correct
7 Correct 299 ms 41668 KB Output is correct
8 Correct 283 ms 40864 KB Output is correct
9 Correct 269 ms 35884 KB Output is correct
10 Correct 275 ms 37924 KB Output is correct
11 Correct 244 ms 31632 KB Output is correct
12 Correct 244 ms 32032 KB Output is correct
13 Correct 266 ms 36928 KB Output is correct
14 Correct 244 ms 32672 KB Output is correct
15 Correct 272 ms 38612 KB Output is correct
16 Correct 18 ms 5972 KB Output is correct
17 Correct 330 ms 46972 KB Output is correct
18 Correct 219 ms 30000 KB Output is correct
19 Correct 62 ms 11836 KB Output is correct
20 Correct 74 ms 13568 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8000 KB Output is correct
2 Correct 76 ms 9344 KB Output is correct
3 Correct 71 ms 7744 KB Output is correct
4 Correct 40 ms 5192 KB Output is correct
5 Correct 57 ms 7472 KB Output is correct
6 Correct 51 ms 5404 KB Output is correct
7 Correct 52 ms 6592 KB Output is correct
8 Correct 49 ms 7648 KB Output is correct
9 Correct 51 ms 8296 KB Output is correct
10 Correct 38 ms 6080 KB Output is correct
11 Correct 39 ms 6336 KB Output is correct
12 Correct 36 ms 6080 KB Output is correct
13 Correct 39 ms 6344 KB Output is correct
14 Correct 39 ms 6324 KB Output is correct
15 Correct 37 ms 6052 KB Output is correct
16 Correct 9 ms 3224 KB Output is correct
17 Correct 59 ms 11892 KB Output is correct
18 Correct 39 ms 6324 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 19868 KB Output is correct
2 Correct 304 ms 20904 KB Output is correct
3 Correct 290 ms 20100 KB Output is correct
4 Correct 267 ms 19976 KB Output is correct
5 Correct 281 ms 20716 KB Output is correct
6 Correct 274 ms 19992 KB Output is correct
7 Correct 291 ms 20876 KB Output is correct
8 Correct 270 ms 20256 KB Output is correct
9 Correct 274 ms 19912 KB Output is correct
10 Correct 276 ms 20272 KB Output is correct
11 Correct 273 ms 20216 KB Output is correct
12 Correct 266 ms 19976 KB Output is correct
13 Correct 276 ms 20280 KB Output is correct
14 Correct 277 ms 20496 KB Output is correct
15 Correct 277 ms 20756 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 267 ms 20236 KB Output is correct
18 Correct 269 ms 20096 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 350 ms 33460 KB Output is correct
22 Correct 339 ms 49568 KB Output is correct
23 Correct 318 ms 38880 KB Output is correct
24 Correct 269 ms 35744 KB Output is correct
25 Correct 315 ms 36756 KB Output is correct
26 Correct 275 ms 35368 KB Output is correct
27 Correct 299 ms 41668 KB Output is correct
28 Correct 283 ms 40864 KB Output is correct
29 Correct 269 ms 35884 KB Output is correct
30 Correct 275 ms 37924 KB Output is correct
31 Correct 244 ms 31632 KB Output is correct
32 Correct 244 ms 32032 KB Output is correct
33 Correct 266 ms 36928 KB Output is correct
34 Correct 244 ms 32672 KB Output is correct
35 Correct 272 ms 38612 KB Output is correct
36 Correct 18 ms 5972 KB Output is correct
37 Correct 330 ms 46972 KB Output is correct
38 Correct 219 ms 30000 KB Output is correct
39 Correct 62 ms 11836 KB Output is correct
40 Correct 74 ms 13568 KB Output is correct
41 Correct 72 ms 8000 KB Output is correct
42 Correct 76 ms 9344 KB Output is correct
43 Correct 71 ms 7744 KB Output is correct
44 Correct 40 ms 5192 KB Output is correct
45 Correct 57 ms 7472 KB Output is correct
46 Correct 51 ms 5404 KB Output is correct
47 Correct 52 ms 6592 KB Output is correct
48 Correct 49 ms 7648 KB Output is correct
49 Correct 51 ms 8296 KB Output is correct
50 Correct 38 ms 6080 KB Output is correct
51 Correct 39 ms 6336 KB Output is correct
52 Correct 36 ms 6080 KB Output is correct
53 Correct 39 ms 6344 KB Output is correct
54 Correct 39 ms 6324 KB Output is correct
55 Correct 37 ms 6052 KB Output is correct
56 Correct 9 ms 3224 KB Output is correct
57 Correct 59 ms 11892 KB Output is correct
58 Correct 39 ms 6324 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 483 ms 47356 KB Output is correct
62 Correct 500 ms 49416 KB Output is correct
63 Correct 491 ms 45088 KB Output is correct
64 Correct 366 ms 41552 KB Output is correct
65 Correct 394 ms 43344 KB Output is correct
66 Correct 371 ms 41476 KB Output is correct
67 Correct 368 ms 41216 KB Output is correct
68 Correct 369 ms 40496 KB Output is correct
69 Correct 380 ms 40936 KB Output is correct
70 Correct 357 ms 38300 KB Output is correct
71 Correct 338 ms 37052 KB Output is correct
72 Correct 378 ms 38076 KB Output is correct
73 Correct 343 ms 37628 KB Output is correct
74 Correct 345 ms 38816 KB Output is correct
75 Correct 348 ms 38816 KB Output is correct
76 Correct 19 ms 5972 KB Output is correct
77 Correct 366 ms 47240 KB Output is correct
78 Correct 311 ms 35736 KB Output is correct
79 Correct 1 ms 212 KB Output is correct
80 Correct 0 ms 212 KB Output is correct