Submission #894314

#	Time	Username	Problem	Language	Result	Execution time	Memory
894314		vjudge1	Index (COCI21_index)	C++17	60 / 110	2562 ms	7100 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50