oj.uz

Submission #894316

# Submission time Handle Problem Language Result Execution time Memory
894316 2023-12-28T05:24:12 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 827 ms 6976 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <climits>
#include <random>
using namespace std;
   
#define ll long long
#define pb push_back
#define ull unsigned long long
#define F first
#define S second
#define all(v) v.begin(), v.end()

const int INF = INT_MAX;
const int block = 500;

int t[200005], n, q;
int a[200001], ans[200001];

void upd(int i, int x){
    for(; i < 200005; i = (i | (i + 1)))
        t[i] += x;
}

int get(int r){
    int ret = 0;
    for(; r >= 0; r = ((r & (r + 1)) - 1)){
        ret += t[r];
    }
    return ret;
}

int get(int l, int r){
    return get(r) - get(l - 1);
}

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    if(a.F.F / block == b.F.F / block)
        return a.F.S < b.F.S;
    return ((a.F.F / block) < (b.F.F / block));
}

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<pair<pair<int, int>, int>> query;
    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        query.pb({{l, r}, i});
    }
    sort(all(query), cmp);
    int l = 1, r = 0;
    for(auto [p, i] : query){
        auto [tl, tr] = p;
        while(l > tl){
            l--;
            upd(a[l], 1);
        }
        while(r < tr){
            r++;
            upd(a[r], 1);
        }
        while(l < tl){
            upd(a[l], -1);
            l++;
        }
        while(r > tr){
            upd(a[r], -1);
            r--;
        }
        int L = 1, R = n + 1;
        while(R - L > 1){
            int mid = (L + R) / 2;
            if(mid <= get(mid, n)) L = mid;
            else R = mid;
        }
        ans[i] = L;
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int xach = 1; 
    //cin >> xach;
    while(xach--) solve();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 154 ms 3528 KB Output is correct
12 Correct 150 ms 3788 KB Output is correct
13 Correct 150 ms 3648 KB Output is correct
14 Correct 151 ms 3528 KB Output is correct
15 Correct 151 ms 3524 KB Output is correct
16 Correct 148 ms 3528 KB Output is correct
17 Correct 151 ms 3532 KB Output is correct
18 Correct 153 ms 3652 KB Output is correct
19 Correct 152 ms 3528 KB Output is correct
20 Correct 154 ms 3532 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 154 ms 3528 KB Output is correct
12 Correct 150 ms 3788 KB Output is correct
13 Correct 150 ms 3648 KB Output is correct
14 Correct 151 ms 3528 KB Output is correct
15 Correct 151 ms 3524 KB Output is correct
16 Correct 148 ms 3528 KB Output is correct
17 Correct 151 ms 3532 KB Output is correct
18 Correct 153 ms 3652 KB Output is correct
19 Correct 152 ms 3528 KB Output is correct
20 Correct 154 ms 3532 KB Output is correct
21 Correct 810 ms 6296 KB Output is correct
22 Correct 820 ms 6292 KB Output is correct
23 Correct 810 ms 6340 KB Output is correct
24 Correct 827 ms 6352 KB Output is correct
25 Correct 810 ms 6352 KB Output is correct
26 Correct 811 ms 6292 KB Output is correct
27 Correct 811 ms 6608 KB Output is correct
28 Correct 816 ms 6480 KB Output is correct
29 Correct 827 ms 6436 KB Output is correct
30 Correct 826 ms 6976 KB Output is correct