Submission #1304848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304848		Hamed_Ghaffari	Index (COCI21_index)	C++20	110 / 110	778 ms	23448 KiB

index

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#ifdef HAMED
#define DB 1
#else
#define DB 0
#endif
#define debug           if(DB) cout
#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)>>1)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int LOG = 23;

int n, q, p[MXN], ql[MXN], qr[MXN], L[MXN], R[MXN];
vector<int> pos[MXN], vec[MXN];

int fen[MXN];
void updx(int p, int x) {
    for(; p<=n; p+=p&-p) fen[p] += x;
}
int getx(int l, int r) {
    int res = 0;
    for(; r; r-=r&-r) res += fen[r];
    for(--l; l; l-=l&-l) res -= fen[l];
    return res;
}

void Main() {
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> p[i];
        pos[p[i]].push_back(i);
    }
    for(int i=1; i<=q; i++) {
        cin >> ql[i] >> qr[i];
        L[i] = 1; R[i] = qr[i]-ql[i]+2;
    }
    while(1) {
        bool fnd = 0;
        for(int i=1; i<=n; i++) vec[i].clear();
        for(int i=1; i<=q; i++)
            if(R[i]-L[i]>1)
                vec[(L[i]+R[i])>>1].push_back(i),
                fnd = 1;
        if(!fnd) break;
        fill(fen+1, fen+n+1, 0);
        for(int i=n; i>=1; i--) {
            for(int j : pos[i]) updx(j, 1);
            for(int j : vec[i])
                (getx(ql[j], qr[j])>=i ? L : R)[j] = i;
        }
    }
    for(int i=1; i<=q; i++) cout << L[i] << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50