oj.uz

Submission #391944

# Submission time Handle Problem Language Result Execution time Memory
391944 2021-04-20T08:32:34 Z Jarif_Rahman Index (COCI21_index) C++17
110 / 110
 1650 ms 12288 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int sq = 417, lim = 524288;
bool mo(tuple<int, int, int> a, tuple<int, int, int> b){
    return make_pair(get<0>(a)/sq, get<1>(a)) < make_pair(get<0>(b)/sq, get<1>(b));
}
struct segtree{
    int k;
    ll sm[lim];
    segtree(int n){
        k = lim;
    }
    void upd(int in, ll x){
        in+=k/2;
        sm[in] = x, in/=2;
        while(in > 0){
            sm[in] = sm[2*in] + sm[2*in+1];
            in/=2;
        }
    }
    inline ll sum(int l, int r, int nd, int a, int b){
        if(b < l || a > r) return 0;
        if(a >= l && b <= r) return sm[nd];
        int c = (a+b)/2;
        return sum(l, r, 2*nd, a, c) + sum(l, r, 2*nd+1, c+1, b);
    }
    inline ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1);
    }
    inline ll ans(int a, int b, int nd, ll s){
        if(nd >= k/2) return a;
        int md = (a+b)/2;
        if(s+sm[2*nd+1] >= md+1) return ans(md+1, b, 2*nd+1, s);
        return ans(a, md, 2*nd, s+sm[2*nd+1]);
    }
    ll get(int in){
        return sm[k/2+in];
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    int v[n];
    for(int &x: v) cin >> x;
    tuple<int, int, int> query[q];
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r; l--, r--;
        query[i] = {l, r, i};
    }
    vector<int> ans(q);
    sort(query, query+q, mo);
    segtree pp(lim);
    int a = 0, b = 0;
    pp.upd(v[0], pp.get(v[0])+1);
    for(auto [l, r, in]: query){
        for(int i = a; i < l; i++) pp.upd(v[i], pp.get(v[i])-1);
        for(int i = a-1; i >= l; i--) pp.upd(v[i], pp.get(v[i])+1);
        for(int i = b+1; i <= r; i++) pp.upd(v[i], pp.get(v[i])+1);
        for(int i = b; i > r; i--) pp.upd(v[i], pp.get(v[i])-1);
        a = l, b = r;
        ans[in] = pp.ans(0, pp.k/2-1, 1, 0);
    }
    for(int x: ans) cout << x << "\n";
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:42:25: warning: 'pp.segtree::sm[<unknown>]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |         return sm[k/2+in];
      |                         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 357 ms 3200 KB Output is correct
12 Correct 368 ms 3216 KB Output is correct
13 Correct 364 ms 3200 KB Output is correct
14 Correct 393 ms 3240 KB Output is correct
15 Correct 353 ms 3196 KB Output is correct
16 Correct 358 ms 3192 KB Output is correct
17 Correct 360 ms 3216 KB Output is correct
18 Correct 361 ms 3200 KB Output is correct
19 Correct 354 ms 3208 KB Output is correct
20 Correct 355 ms 3212 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 357 ms 3200 KB Output is correct
12 Correct 368 ms 3216 KB Output is correct
13 Correct 364 ms 3200 KB Output is correct
14 Correct 393 ms 3240 KB Output is correct
15 Correct 353 ms 3196 KB Output is correct
16 Correct 358 ms 3192 KB Output is correct
17 Correct 360 ms 3216 KB Output is correct
18 Correct 361 ms 3200 KB Output is correct
19 Correct 354 ms 3208 KB Output is correct
20 Correct 355 ms 3212 KB Output is correct
21 Correct 1648 ms 12268 KB Output is correct
22 Correct 1633 ms 12252 KB Output is correct
23 Correct 1630 ms 12252 KB Output is correct
24 Correct 1626 ms 12228 KB Output is correct
25 Correct 1650 ms 12256 KB Output is correct
26 Correct 1595 ms 12244 KB Output is correct
27 Correct 1613 ms 12264 KB Output is correct
28 Correct 1593 ms 12248 KB Output is correct
29 Correct 1574 ms 12256 KB Output is correct
30 Correct 1621 ms 12288 KB Output is correct