Submission #763754

#	Time	Username	Problem	Language	Result	Execution time	Memory
763754		swagchicken	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	768 ms	65036 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  =  1000000007;
#define inf 1e18;
#define INF INT_MAX;
 
long double PI = 4*atan(1);
long double eps = 1e-8;

int N, q;
int n;

vi a;
vector<array<int, 3>> qs;

struct seg {
    int v, l, r;

    bool operator<(const seg& o) const {
        return v < o.v;
    }
};

map<seg, int> segidx;
set<seg> segs;
vector<seg> allsegs;

int st[2000000] = {};

void update(int p, int l, int r, int idx, int v) {
    if(l == r) {
        st[p] = v;
        return;
    }
    int m = (l + r)/2;
    if(idx <= m) {
        update(2*p, l, m, idx, v);
    } else {
        update(2*p + 1, m+1,r, idx, v);
    }
    st[p] = st[2*p] + st[2*p+1];
    return;
}

int query(int p, int l, int r, int v) {
    if(l == r) {
        return a[allsegs[l].l + v - 1];
    }
    int m = (l+r)/2;
    if(st[2*p] >= v) {
        return query(2*p, l, m, v);
    } 
    return query(2*p + 1, m + 1, r, v - st[2*p]);
}


vi bruteans;

vi brute() {
    vi b = a;
    int t = 0;

    vi c = b;
    int qidx = 0;
    vi ans(q);
    while(true) {
        
        while(qidx < q && qs[qidx][0] == t) {
            ans[qs[qidx][2]] = b[qs[qidx][1] - 1];
            qidx++;
        }

        c.clear();
        int lp = 0;
        int rp = 0;
        while(lp < n && rp < n) {
            if(b[lp] < b[n + rp]) {
                c.pb(b[lp]); lp++;
            } else {
                c.pb(b[n + rp]); rp++;
            }
        }
        while(lp < n) {c.pb(b[lp]); lp++;}
        while(rp < n) {c.pb(b[n + rp]); rp++;}

        if(c == b) break;
        b = c;
        t++;
    }

    
    while(qidx < q) {
        ans[qs[qidx][2]] = b[qs[qidx][1] - 1];
        qidx++;
    }
    
    return ans;
    
}
int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    // freopen("promote.in", "r", stdin);
    // freopen("promote.out", "w", stdout);
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif 
    
    
    cin >> N >> q;
    n = N/2;

    a.resize(N); re(a);

    
    FOR(i,0,q) {
        int t,id; cin >> t >> id;
        qs.pb({t, id, i});
    }

    sort(all(qs));

    
    // vi bruteans = brute();

    stack<int> stk;
    vi nxt(N);
    FOR(i,0,N) {
        while(!stk.empty() && a[i] > a[stk.top()]) {
            nxt[stk.top()] = i - 1;
            stk.pop();
        }
        stk.push(i);
    }
    while(!stk.empty()) {
        int c = stk.top(); stk.pop();
        nxt[c] = N-1;
    }

    

    for(int i = 0; i < N; i = nxt[i] + 1) {
        segs.insert({a[i], i, nxt[i]});
        allsegs.pb({a[i], i, nxt[i]});
    }

    int len = N;
    while(len > n) {
        auto p = segs.rbegin();
        int clen = (*p).r - (*p).l + 1;
        while(len - clen >= n) {
            segs.erase(*p);
            len -= clen;
            if(!segs.empty()) p = segs.rbegin();
            clen = (*p).r - (*p).l + 1;
        }

        if(len > n) {
            int l = (*p).l; 
            int r = (*p).r;
            segs.erase(*p);
            
            int r1 = l + n - (len - clen) - 1;
            allsegs.pb({a[l], l, r1});
            segs.insert({a[l], l , r1});
            r1++;
            while(r1 <= r) {
                int r2 = min(nxt[r1], r);
                allsegs.pb({a[r1], r1, r2});
                segs.insert({a[r1], r1, r2});
                r1 = r2 + 1;
            }
        } 
    }

    sort(all(allsegs));
    int m = allsegs.size();
    FOR(i,0,m) segidx[allsegs[i]] = i;

    segs.clear();
    
    vi ans(q);
    int t = 0;
    int qidx = 0;
    
    for(int i = 0; i < N; i = nxt[i] + 1) {
        segs.insert({a[i], i, nxt[i]});
        int segid = segidx[{a[i], i, nxt[i]}];
        update(1, 0, m, segid, nxt[i] - i + 1);
    }

    while(qidx < q && qs[qidx][0] == t) {
        ans[qs[qidx][2]] = query(1, 0, m, qs[qidx][1]);
        qidx++;
    }

    len = N;
    while(len > n) {
        auto p = segs.rbegin();
        int clen = (*p).r - (*p).l + 1;
        while(len - clen >= n) {
            int segid = segidx[*p];
         //   update(1, 0, m, segid, 0);
            segs.erase(*p);
            len -= clen;
            if(!segs.empty()) p = segs.rbegin();
            clen = (*p).r - (*p).l + 1;
        }

        if(len > n) {
            int l = (*p).l; 
            int r = (*p).r;
            int segid = segidx[*p];
            update(1, 0, m, segid, 0);

            segs.erase(*p);
            
            
            int r1 = l + n - (len - clen) - 1;
            segs.insert({a[l], l , r1});

            segid = segidx[{a[l], l , r1}];
            update(1, 0, m, segid, r1 - l + 1);

            r1++;
            while(r1 <= r) {
                int r2 = min(nxt[r1], r);
                segs.insert({a[r1], r1, r2});

                segid = segidx[{a[r1], r1, r2}];
                update(1, 0, m, segid, r2 - r1 + 1);

                r1 = r2 + 1;
            }
        }
        
        t++;

        while(qidx < q && qs[qidx][0] == t) {
            ans[qs[qidx][2]] = query(1, 0, m, qs[qidx][1]);
            qidx++;
        }
    }

    while(qidx < q) {
        ans[qs[qidx][2]] = query(1, 0, m, qs[qidx][1]);
        qidx++;
    }

    FOR(i,0,q) {
        cout << ans[i] << endl;
    }


    





    

    
    // auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    // cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:266:17: warning: unused variable 'segid' [-Wunused-variable]
  266 |             int segid = segidx[*p];
      |                 ^~~~~

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