답안 #1078315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078315	2024-08-27T15:13:21 Z	cpptowin	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	694 ms	125148 KB

Main

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
struct SegmentTree
{
    vector<int> st;
    int n;
    /// real n
    SegmentTree(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10);
    }
    void update(int id, int l, int r, int x, int val)
    {
        if (x > r or x < l)
            return;
        if (l == r)
        {
            st[id] += val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, x, val);
        update(id << 1 | 1, mid + 1, r, x, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    void assign(int id, int l, int r, int x, int val)
    {
        if (x > r or x < l)
            return;
        if (l == r)
        {
            st[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        assign(id << 1, l, mid, x, val);
        assign(id << 1 | 1, mid + 1, r, x, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return 0;
        if (u <= l && r <= v)
            return st[id];
        int mid = (l + r) >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }
    int walkright(int id, int l, int r, int x, int val)
    {
        if (st[id] < val)
            return -1;
        if (r < x)
            return -1;
        if (l == r)
            return l;
        int mid = l + r >> 1;
        int ans = -1;
        if (st[id << 1] >= val)
            return walkright(id << 1, l, mid, x, val);
        return walkright(id << 1 | 1, mid + 1, r, x, val - st[id << 1]);
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int x, int val)
    {
        update(1, 1, n, x, val);
    }
    void assign(int x, int val)
    {
        assign(1, 1, n, x, val);
    }
    int walkright(int x, int val)
    {
        return walkright(1, 1, n, x, val);
    }
} t(maxn);
void R(int a[], int n, int ans[])
{
    stack<int> st;
    fod(i, n, 1)
    {
        while (st.size() and a[st.top()] <= a[i])
            st.pop();
        ans[i] = (st.empty() ? n + 1 : st.top());
        st.push(i);
    }
}
int n, q, a[maxn];
vii qry[maxn];
int r[maxn];
int pos[maxn];
int res[maxn];
set<array<int, 3>> st;
void calc(int ff)
{
    for (auto [p, id] : qry[ff])
    {
        int x = t.walkright(1, p);
        int p1 = p - t.get(1, x - 1);
        res[id] = a[pos[x] + p1 - 1];
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    t.resize(n);
    fo(i, 1, n) cin >> a[i], pos[a[i]] = i;
    fo(i, 1, q)
    {
        int t, u;
        cin >> t >> u;
        if (t == 0)
            res[i] = a[u];
        else
            qry[min(n, t)].pb(u, i);
    }
    R(a, n, r);
    int id = 1;
    while (id <= n)
    {
        st.insert({a[id], id, r[id] - 1});
        t.assign(a[id], r[id] - id);
        id = r[id];
    }
    // for(auto [v,l,r] : st) cout << v << ' ' << l << ' ' << r << "\n";en;
    fo(i, 1, n)
    {
        int p = t.walkright(1, n / 2);
        if (t.get(1, p) > n / 2)
        {
            int p1 = n / 2 - t.get(1, p - 1);
            int ff = t.get(p, p);
            auto lb = st.find({p, pos[p], pos[p] + ff - 1});
            if (lb != st.end())
                st.erase(lb);
            st.insert({p, pos[p], pos[p] + p1 - 1});
            t.assign(p, p1);
            int ind = pos[p] + p1;
            // if(i == 2) cout << p << ' ' << p1 << ' ' << ff << ' ' << r[ind] << "\n";
            while (ind <= pos[p] + ff - 1)
            {
                int pos1 = min(r[ind] - 1,pos[p] + ff - 1);
                st.insert({a[ind], ind, pos1});
                t.assign(a[ind], pos1 - ind + 1);
                ind = r[ind];
            }
        }
        calc(i);
        // for(auto [v,l,r] : st) cout << v << ' ' << l << ' ' << r << "\n";en;
    }
    fo(i, 1, q) cout << res[i] << "\n";
}

Compilation message

Main.cpp: In member function 'long long int SegmentTree::walkright(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:118:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp:119:13: warning: unused variable 'ans' [-Wunused-variable]
  119 |         int ans = -1;
      |             ^~~
Main.cpp: At global scope:
Main.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  167 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	250 ms	94460 KB	Output is correct
2	Correct	285 ms	91984 KB	Output is correct
3	Correct	259 ms	91344 KB	Output is correct
4	Correct	221 ms	88304 KB	Output is correct
5	Correct	230 ms	94872 KB	Output is correct
6	Correct	221 ms	91820 KB	Output is correct
7	Correct	241 ms	96716 KB	Output is correct
8	Correct	226 ms	90148 KB	Output is correct
9	Correct	216 ms	88992 KB	Output is correct
10	Correct	229 ms	89544 KB	Output is correct
11	Correct	214 ms	89540 KB	Output is correct
12	Correct	199 ms	84292 KB	Output is correct
13	Correct	208 ms	87900 KB	Output is correct
14	Correct	226 ms	91348 KB	Output is correct
15	Correct	223 ms	88844 KB	Output is correct
16	Correct	23 ms	55132 KB	Output is correct
17	Correct	135 ms	72408 KB	Output is correct
18	Correct	173 ms	79804 KB	Output is correct
19	Correct	24 ms	55132 KB	Output is correct
20	Correct	20 ms	55132 KB	Output is correct

Subtask #2

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	459 ms	116644 KB	Output is correct
2	Correct	385 ms	115676 KB	Output is correct
3	Correct	433 ms	105968 KB	Output is correct
4	Correct	309 ms	97188 KB	Output is correct
5	Correct	340 ms	98304 KB	Output is correct
6	Correct	354 ms	96424 KB	Output is correct
7	Correct	345 ms	104612 KB	Output is correct
8	Correct	327 ms	103392 KB	Output is correct
9	Correct	307 ms	97444 KB	Output is correct
10	Correct	319 ms	100440 KB	Output is correct
11	Correct	250 ms	92836 KB	Output is correct
12	Correct	264 ms	93092 KB	Output is correct
13	Correct	304 ms	99492 KB	Output is correct
14	Correct	277 ms	93892 KB	Output is correct
15	Correct	314 ms	101536 KB	Output is correct
16	Correct	53 ms	61172 KB	Output is correct
17	Correct	234 ms	94584 KB	Output is correct
18	Correct	231 ms	90528 KB	Output is correct
19	Correct	80 ms	65616 KB	Output is correct
20	Correct	108 ms	70340 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	145 ms	69456 KB	Output is correct
2	Correct	107 ms	69236 KB	Output is correct
3	Correct	123 ms	68932 KB	Output is correct
4	Correct	76 ms	63428 KB	Output is correct
5	Correct	107 ms	66132 KB	Output is correct
6	Correct	78 ms	63568 KB	Output is correct
7	Correct	98 ms	65104 KB	Output is correct
8	Correct	88 ms	64080 KB	Output is correct
9	Correct	99 ms	65108 KB	Output is correct
10	Correct	62 ms	62608 KB	Output is correct
11	Correct	70 ms	63060 KB	Output is correct
12	Correct	66 ms	62804 KB	Output is correct
13	Correct	74 ms	62592 KB	Output is correct
14	Correct	65 ms	62804 KB	Output is correct
15	Correct	60 ms	62544 KB	Output is correct
16	Correct	39 ms	58192 KB	Output is correct
17	Correct	70 ms	66228 KB	Output is correct
18	Correct	50 ms	60872 KB	Output is correct
19	Correct	21 ms	55132 KB	Output is correct
20	Correct	24 ms	55132 KB	Output is correct

Subtask #4

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	250 ms	94460 KB	Output is correct
2	Correct	285 ms	91984 KB	Output is correct
3	Correct	259 ms	91344 KB	Output is correct
4	Correct	221 ms	88304 KB	Output is correct
5	Correct	230 ms	94872 KB	Output is correct
6	Correct	221 ms	91820 KB	Output is correct
7	Correct	241 ms	96716 KB	Output is correct
8	Correct	226 ms	90148 KB	Output is correct
9	Correct	216 ms	88992 KB	Output is correct
10	Correct	229 ms	89544 KB	Output is correct
11	Correct	214 ms	89540 KB	Output is correct
12	Correct	199 ms	84292 KB	Output is correct
13	Correct	208 ms	87900 KB	Output is correct
14	Correct	226 ms	91348 KB	Output is correct
15	Correct	223 ms	88844 KB	Output is correct
16	Correct	23 ms	55132 KB	Output is correct
17	Correct	135 ms	72408 KB	Output is correct
18	Correct	173 ms	79804 KB	Output is correct
19	Correct	24 ms	55132 KB	Output is correct
20	Correct	20 ms	55132 KB	Output is correct
21	Correct	459 ms	116644 KB	Output is correct
22	Correct	385 ms	115676 KB	Output is correct
23	Correct	433 ms	105968 KB	Output is correct
24	Correct	309 ms	97188 KB	Output is correct
25	Correct	340 ms	98304 KB	Output is correct
26	Correct	354 ms	96424 KB	Output is correct
27	Correct	345 ms	104612 KB	Output is correct
28	Correct	327 ms	103392 KB	Output is correct
29	Correct	307 ms	97444 KB	Output is correct
30	Correct	319 ms	100440 KB	Output is correct
31	Correct	250 ms	92836 KB	Output is correct
32	Correct	264 ms	93092 KB	Output is correct
33	Correct	304 ms	99492 KB	Output is correct
34	Correct	277 ms	93892 KB	Output is correct
35	Correct	314 ms	101536 KB	Output is correct
36	Correct	53 ms	61172 KB	Output is correct
37	Correct	234 ms	94584 KB	Output is correct
38	Correct	231 ms	90528 KB	Output is correct
39	Correct	80 ms	65616 KB	Output is correct
40	Correct	108 ms	70340 KB	Output is correct
41	Correct	145 ms	69456 KB	Output is correct
42	Correct	107 ms	69236 KB	Output is correct
43	Correct	123 ms	68932 KB	Output is correct
44	Correct	76 ms	63428 KB	Output is correct
45	Correct	107 ms	66132 KB	Output is correct
46	Correct	78 ms	63568 KB	Output is correct
47	Correct	98 ms	65104 KB	Output is correct
48	Correct	88 ms	64080 KB	Output is correct
49	Correct	99 ms	65108 KB	Output is correct
50	Correct	62 ms	62608 KB	Output is correct
51	Correct	70 ms	63060 KB	Output is correct
52	Correct	66 ms	62804 KB	Output is correct
53	Correct	74 ms	62592 KB	Output is correct
54	Correct	65 ms	62804 KB	Output is correct
55	Correct	60 ms	62544 KB	Output is correct
56	Correct	39 ms	58192 KB	Output is correct
57	Correct	70 ms	66228 KB	Output is correct
58	Correct	50 ms	60872 KB	Output is correct
59	Correct	21 ms	55132 KB	Output is correct
60	Correct	24 ms	55132 KB	Output is correct
61	Correct	694 ms	125148 KB	Output is correct
62	Correct	623 ms	123532 KB	Output is correct
63	Correct	642 ms	121044 KB	Output is correct
64	Correct	487 ms	111896 KB	Output is correct
65	Correct	513 ms	114380 KB	Output is correct
66	Correct	504 ms	111824 KB	Output is correct
67	Correct	442 ms	110540 KB	Output is correct
68	Correct	467 ms	108116 KB	Output is correct
69	Correct	491 ms	111976 KB	Output is correct
70	Correct	401 ms	105680 KB	Output is correct
71	Correct	341 ms	108412 KB	Output is correct
72	Correct	403 ms	106444 KB	Output is correct
73	Correct	389 ms	107212 KB	Output is correct
74	Correct	392 ms	110800 KB	Output is correct
75	Correct	381 ms	107316 KB	Output is correct
76	Correct	57 ms	61008 KB	Output is correct
77	Correct	250 ms	95032 KB	Output is correct
78	Correct	246 ms	90552 KB	Output is correct
79	Correct	22 ms	55132 KB	Output is correct
80	Correct	22 ms	55192 KB	Output is correct