oj.uz

Submission #894467

# Submission time Handle Problem Language Result Execution time Memory
894467 2023-12-28T10:19:31 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 331 ms 10388 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 3 ms 2560 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 2 ms 2560 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 3 ms 2560 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 2 ms 2560 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 79 ms 4040 KB Output is correct
12 Correct 81 ms 4300 KB Output is correct
13 Correct 81 ms 4208 KB Output is correct
14 Correct 81 ms 4208 KB Output is correct
15 Correct 77 ms 4036 KB Output is correct
16 Correct 80 ms 4044 KB Output is correct
17 Correct 86 ms 4212 KB Output is correct
18 Correct 77 ms 4224 KB Output is correct
19 Correct 78 ms 4208 KB Output is correct
20 Correct 77 ms 4040 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 3 ms 2560 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 2 ms 2560 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 79 ms 4040 KB Output is correct
12 Correct 81 ms 4300 KB Output is correct
13 Correct 81 ms 4208 KB Output is correct
14 Correct 81 ms 4208 KB Output is correct
15 Correct 77 ms 4036 KB Output is correct
16 Correct 80 ms 4044 KB Output is correct
17 Correct 86 ms 4212 KB Output is correct
18 Correct 77 ms 4224 KB Output is correct
19 Correct 78 ms 4208 KB Output is correct
20 Correct 77 ms 4040 KB Output is correct
21 Correct 311 ms 8692 KB Output is correct
22 Correct 298 ms 9668 KB Output is correct
23 Correct 302 ms 9404 KB Output is correct
24 Correct 331 ms 9496 KB Output is correct
25 Correct 302 ms 10388 KB Output is correct
26 Correct 296 ms 9372 KB Output is correct
27 Correct 304 ms 9376 KB Output is correct
28 Correct 294 ms 9408 KB Output is correct
29 Correct 295 ms 9404 KB Output is correct
30 Correct 305 ms 9368 KB Output is correct