oj.uz

Submission #894314

# Submission time Handle Problem Language Result Execution time Memory
894314 2023-12-28T05:20:29 Z vjudge1 Index (COCI21_index) C++17
60 / 110
 2500 ms 7100 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[200001 * 4], n, q;
int a[200001], ans[200001];

int get(int l, int r, int v = 1, int tl = 1, int tr = n){
    if(r < tl || tr < l) return 0;
    if(l <= tl && tr <= r) return t[v];
    int m = (tl + tr) / 2;
    return get(l, r, v * 2, tl, m) + get(l, r, v * 2 + 1, m + 1, tr);
}

void upd(int idx, int x, int v = 1, int l = 1, int r = n){
    if(l == r) t[v] += x;
    else{
        int m = (l + r) / 2;
        if(idx <= m) upd(idx, x, v * 2, l, m);
        else upd(idx, x, v * 2 + 1, m + 1, r);
        t[v] = t[v * 2] + t[v * 2 + 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 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2544 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2400 KB Output is correct
6 Correct 2 ms 2544 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 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 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2544 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2400 KB Output is correct
6 Correct 2 ms 2544 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 796 ms 3656 KB Output is correct
12 Correct 789 ms 3656 KB Output is correct
13 Correct 782 ms 3672 KB Output is correct
14 Correct 796 ms 3532 KB Output is correct
15 Correct 804 ms 3660 KB Output is correct
16 Correct 799 ms 3656 KB Output is correct
17 Correct 820 ms 3664 KB Output is correct
18 Correct 798 ms 3668 KB Output is correct
19 Correct 814 ms 3660 KB Output is correct
20 Correct 788 ms 3652 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2544 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2400 KB Output is correct
6 Correct 2 ms 2544 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 796 ms 3656 KB Output is correct
12 Correct 789 ms 3656 KB Output is correct
13 Correct 782 ms 3672 KB Output is correct
14 Correct 796 ms 3532 KB Output is correct
15 Correct 804 ms 3660 KB Output is correct
16 Correct 799 ms 3656 KB Output is correct
17 Correct 820 ms 3664 KB Output is correct
18 Correct 798 ms 3668 KB Output is correct
19 Correct 814 ms 3660 KB Output is correct
20 Correct 788 ms 3652 KB Output is correct
21 Execution timed out 2562 ms 7100 KB Time limit exceeded
22 Halted 0 ms 0 KB -