oj.uz

Submission #1012032

# Submission time Handle Problem Language Result Execution time Memory
1012032 2024-07-01T14:43:20 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 219 ms 33944 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = (n) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX         200005
#define N           200000
int nArr, numQuery;

int A[MAX];
int L[MAX], R[MAX];
int F[MAX];
int low_bit(int p){
    return (p & (-p));
}
void upd(int p, int val){
    for (; p <= N; p += low_bit(p)){
        F[p] += val;
    }
}

int query(int p){
    int res = 0;
    for (; p > 0; p -= low_bit(p)){
        res += F[p];
    }
    return res;
}
int query(int l, int r){
    return query(r) - query(l - 1);
}
vector<int> val[MAX];
int ans[MAX];
void parallel(int l, int r, vector<int>&cand){
    //solve for segment [l, r)
    if (l + 1 == r || cand.empty()){
        for (int&i : cand) ans[i] = l;
        return;
    }
    int m = (l + r) >> 1;
    for (int i = m; i < r; ++i){
        for (int &j : val[i]){
            upd(j, 1);
        }
    }
    vector<int> ok, not_ok;
    for (int &i : cand){
        if (query(L[i], R[i]) >= m){
            ok.emplace_back(i);
        }
        else not_ok.emplace_back(i);
    }
    parallel(l, m, not_ok);
    for (int i = m; i < r; ++i){
        for (int &j : val[i]){
            upd(j, -1);
        }
    }
    parallel(m, r, ok);
}
void process(void){
    cin >> nArr >> numQuery;
    int lim = 0;
    for (int i = 1; i <= nArr; ++i){
        cin >> A[i], maximize(lim, A[i]);
        val[A[i]].emplace_back(i);
    }

    for (int i = 1; i <= numQuery; ++i) cin >> L[i] >> R[i];

    vector<int> cand;
    for (int i = 1; i <= numQuery; ++i) cand.push_back(i);
    parallel(1, lim + 1, cand);

    for (int i = 1; i <= numQuery; ++i){
        cout << ans[i] << "\n";
    }
}

signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);

    process();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 6788 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 6788 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct
11 Correct 42 ms 15064 KB Output is correct
12 Correct 42 ms 14824 KB Output is correct
13 Correct 44 ms 14820 KB Output is correct
14 Correct 42 ms 14944 KB Output is correct
15 Correct 42 ms 14792 KB Output is correct
16 Correct 46 ms 13328 KB Output is correct
17 Correct 42 ms 13516 KB Output is correct
18 Correct 42 ms 13260 KB Output is correct
19 Correct 43 ms 13312 KB Output is correct
20 Correct 45 ms 14800 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 6788 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct
11 Correct 42 ms 15064 KB Output is correct
12 Correct 42 ms 14824 KB Output is correct
13 Correct 44 ms 14820 KB Output is correct
14 Correct 42 ms 14944 KB Output is correct
15 Correct 42 ms 14792 KB Output is correct
16 Correct 46 ms 13328 KB Output is correct
17 Correct 42 ms 13516 KB Output is correct
18 Correct 42 ms 13260 KB Output is correct
19 Correct 43 ms 13312 KB Output is correct
20 Correct 45 ms 14800 KB Output is correct
21 Correct 211 ms 33672 KB Output is correct
22 Correct 199 ms 33644 KB Output is correct
23 Correct 215 ms 33780 KB Output is correct
24 Correct 203 ms 33444 KB Output is correct
25 Correct 213 ms 33848 KB Output is correct
26 Correct 208 ms 33472 KB Output is correct
27 Correct 219 ms 33492 KB Output is correct
28 Correct 199 ms 33944 KB Output is correct
29 Correct 195 ms 33224 KB Output is correct
30 Correct 194 ms 33824 KB Output is correct