oj.uz

Submission #839401

# Submission time Handle Problem Language Result Execution time Memory
839401 2023-08-30T01:25:24 Z abysmal Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 20740 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;
        int sz = perma.size();
        Thing mid = Thing(-1, -1, -1);
        set<Thing>::iterator id = prev(s.end());
        for(set<Thing>::iterator it = s.begin(); it != s.end(); it++)
        {
            int len = (*it).r - (*it).l + 1;
            if(tmp < n / 2 && tmp + len >= n / 2)
            {
                x = (*it).l + (n / 2 - tmp);
                mid = (*it);
            }

            tmp += len;
        }

        do
        {
            tmp -= ((*id).r - (*id).l + 1);
            if(tmp >= n / 2) perma.push_back((*id));
            id = prev(id);
        } while(id != s.begin() && tmp < n / 2);

        for(int i = sz; i < (int) perma.size(); i++)
        {
            s.erase(perma[i]);
            sum -= (perma[i].r - perma[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 263 ms 20044 KB Output is correct
2 Correct 273 ms 20280 KB Output is correct
3 Correct 262 ms 19416 KB Output is correct
4 Correct 254 ms 19140 KB Output is correct
5 Correct 265 ms 19968 KB Output is correct
6 Correct 259 ms 19228 KB Output is correct
7 Correct 271 ms 20084 KB Output is correct
8 Correct 252 ms 19296 KB Output is correct
9 Correct 254 ms 19104 KB Output is correct
10 Correct 260 ms 19484 KB Output is correct
11 Correct 257 ms 19472 KB Output is correct
12 Correct 251 ms 19212 KB Output is correct
13 Correct 270 ms 19560 KB Output is correct
14 Correct 254 ms 19740 KB Output is correct
15 Correct 260 ms 20000 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 242 ms 19484 KB Output is correct
18 Correct 247 ms 19232 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 3025 ms 20740 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 3035 ms 4420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 20044 KB Output is correct
2 Correct 273 ms 20280 KB Output is correct
3 Correct 262 ms 19416 KB Output is correct
4 Correct 254 ms 19140 KB Output is correct
5 Correct 265 ms 19968 KB Output is correct
6 Correct 259 ms 19228 KB Output is correct
7 Correct 271 ms 20084 KB Output is correct
8 Correct 252 ms 19296 KB Output is correct
9 Correct 254 ms 19104 KB Output is correct
10 Correct 260 ms 19484 KB Output is correct
11 Correct 257 ms 19472 KB Output is correct
12 Correct 251 ms 19212 KB Output is correct
13 Correct 270 ms 19560 KB Output is correct
14 Correct 254 ms 19740 KB Output is correct
15 Correct 260 ms 20000 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 242 ms 19484 KB Output is correct
18 Correct 247 ms 19232 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 3025 ms 20740 KB Time limit exceeded
22 Halted 0 ms 0 KB -