Submission #894467

#	Time	Username	Problem	Language	Result	Execution time	Memory
894467		vjudge1	Index (COCI21_index)	C++17	110 / 110	331 ms	10388 KiB

index

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

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ppb pop_back()

const int N = (int)2e5 + 5;
const ll mod = (int)1e9 + 7;
const ll inf = (int)(1e9) + 100;
const int K = 500;

ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n == 1) return a;
    int v = binpow(a, n / 2);
    if (n & 1) return (((v * v) % mod) * a) % mod;
    return (v * v) % mod;
}

ll add(ll a, ll b) {
    return ((a + b) % mod);
}

struct otr {
    int l, r, id;
};

bool cmp(otr A, otr B) {
    if (A.l / K == B.l / K) return A.r < B.r;
    return A.l / K < B.l / K;
}

int a[N], cnt[N], c[K], n, q, ans[N];

void add(int x) {
    x = a[x];
    cnt[x]++;
    c[x / K]++;
}

void del(int x) {
    x = a[x];
    cnt[x]--;
    c[x / K]--;
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<otr> e;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        e.pb({l, r, i});
    }
    sort(all(e), cmp);
    int l = 1, r = 0;
    for (auto [L, R, id] : e) {
        while (r < R) {
            add(++r);
        }
        while (l < L) {
            del(l++);
        }
        while (r > R) {
            del(r--);
        }
        while (l > L) {
            add(--l);
        }
        int h = 0, suf = 0;
        for (int i = K - 2; i >= 0; --i) {
                int cur = min(suf + c[i], i * K);
            if (suf + c[i] >= i * K) {
                cur = h;
                for (int j = (i + 1) * K - 1; j >= i * K; --j) {
                    if (!cnt[j]) continue;
                    suf += cnt[j];
                    cur = min(suf, j);
                    h = max(h, cur);
                }

                break;
            }
            suf += c[i];
            h = max(h, cur);
        }
        ans[id] = h;
     }
     for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

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