oj.uz

Submission #839400

# Submission time Handle Problem Language Result Execution time Memory
839400 2023-08-30T01:15:30 Z abysmal Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 27296 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 q;
    int sum;
    vector<int> a;
    vector<int> nx;
    vector<Query> v;
    vector<Thing> perma;
    Solution() {}

    void solve()
    {
        cin >> n >> q;
        a.resize(n, 0);
        nx.resize(n, n - 1);
        for(int i = 0; i < n; i++)
        {
            cin >> a[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 - 1, i));
        }
        sort(v.begin(), v.end());

        sum = n;
        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 id = 0;
        set<Thing> st;
        while(id < n)
        {
            st.insert(Thing(a[id], id, nx[id]));

            id = nx[id] + 1;
        }

        vector<int> ans(q, -1);
        int x = 0;
        for(int i = 0; i <= n; i++)
        {
//            int tt = 0;
//            for(set<Thing>::iterator it = st.begin(); it != st.end(); it++)
//            {
//                cerr << "tmp = " << tt << "\n";
//                cerr << (*it).val << " " << (*it).l << " " << (*it).r << "\n";
//                tt += ((*it).r - (*it).l + 1);
//            }
//
//            for(int j = perma.size() - 1; j >= 0; j--)
//            {
//                cerr << "tmpp = " << tt << "\n";
//                cerr << perma[j].val << " " << perma[j].l << " " << perma[j].r << "\n";
//                tt += perma[j].r - perma[j].l + 1;
//            }
//            cerr << "\n";
            if(x < q && v[x].t == i)
            {
                int tmp = 0;
                for(set<Thing>::iterator it = st.begin(); it != st.end(); it++)
                {
                    int len = (*it).r - (*it).l + 1;
                    while(x < q && v[x].t == i && tmp + len > v[x].k)
                    {
                        int r = v[x].k - tmp;
                        ans[v[x].id] = a[(*it).l + r];
                        x++;
                    }

                    tmp += len;
                }

                for(int j = perma.size() - 1; j >= 0; j--)
                {
                    int len = perma[j].r - perma[j].l + 1;
                    while(x < q && v[x].t == i && tmp + len > v[x].k)
                    {
                        int r = v[x].k - tmp;
                        ans[v[x].id] = a[perma[j].l + r];
                        x++;
                    }
                    tmp += len;
                }
            }

            Shuffle(st);
        }

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

    void Shuffle(set<Thing>& s)
    {
        if(sum <= n / 2) return;

        int x = 0;
        int tmp = 0;
        Thing mid = Thing(-1, -1, -1);
        vector<Thing> t;
        for(set<Thing>::iterator it = s.begin(); it != s.end(); it++)
        {
            int len = (*it).r - (*it).l + 1;
            if(tmp >= n / 2) t.push_back((*it));
            if(tmp < n / 2 && tmp + len >= n / 2)
            {
                x = (*it).l + (n / 2 - tmp);
                mid = (*it);
            }

            tmp += len;
        }
        reverse(t.begin(), t.end());

        for(int i = 0; i < (int) t.size(); i++)
        {
            s.erase(t[i]);
            perma.push_back(t[i]);
            sum -= (t[i].r - t[i].l + 1);
        }

        if(mid.val == -1) return;
        s.erase(mid);
        s.insert(Thing(mid.val, mid.l, x - 1));
        while(x <= mid.r)
        {
            s.insert(Thing(a[x], x, min(nx[x], mid.r)));
            x = nx[x] + 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 262 ms 19888 KB Output is correct
2 Correct 269 ms 27296 KB Output is correct
3 Correct 274 ms 26272 KB Output is correct
4 Correct 262 ms 25068 KB Output is correct
5 Correct 273 ms 27000 KB Output is correct
6 Correct 248 ms 25372 KB Output is correct
7 Correct 290 ms 27056 KB Output is correct
8 Correct 258 ms 25500 KB Output is correct
9 Correct 252 ms 25192 KB Output is correct
10 Correct 268 ms 25692 KB Output is correct
11 Correct 263 ms 25624 KB Output is correct
12 Correct 252 ms 24476 KB Output is correct
13 Correct 256 ms 25372 KB Output is correct
14 Correct 284 ms 26212 KB Output is correct
15 Correct 277 ms 26076 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 241 ms 25028 KB Output is correct
18 Correct 252 ms 24624 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 20804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 4312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 19888 KB Output is correct
2 Correct 269 ms 27296 KB Output is correct
3 Correct 274 ms 26272 KB Output is correct
4 Correct 262 ms 25068 KB Output is correct
5 Correct 273 ms 27000 KB Output is correct
6 Correct 248 ms 25372 KB Output is correct
7 Correct 290 ms 27056 KB Output is correct
8 Correct 258 ms 25500 KB Output is correct
9 Correct 252 ms 25192 KB Output is correct
10 Correct 268 ms 25692 KB Output is correct
11 Correct 263 ms 25624 KB Output is correct
12 Correct 252 ms 24476 KB Output is correct
13 Correct 256 ms 25372 KB Output is correct
14 Correct 284 ms 26212 KB Output is correct
15 Correct 277 ms 26076 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 241 ms 25028 KB Output is correct
18 Correct 252 ms 24624 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Execution timed out 3070 ms 20804 KB Time limit exceeded
22 Halted 0 ms 0 KB -