Submission #894284

#	Time	Username	Problem	Language	Result	Execution time	Memory
894284		vjudge1	Index (COCI21_index)	C++17	60 / 110	2604 ms	48584 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>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
 
using namespace std;
 
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end() 
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
const int mod = (int) 1e9 + 7;
const int bruh = 450;
 
int a[200001], n;
vector<int> t[200001 * 4];

void build(int v = 1, int l = 1, int r = n){
    if(l == r){
        t[v].pb(a[l]);
    }
    else{
        int m = (l + r) / 2;
        build(v * 2, l, m), build(v * 2 + 1, m + 1, r);
        t[v].resize(t[v * 2].size() + t[v * 2 + 1].size());
        merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin());
    }
}

int get(int x, 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){
        int val = lower_bound(all(t[v]), x) - t[v].begin();
        return t[v].size() - val;
    }
    int m = (tl + tr) / 2;
    return get(x, l, r, v * 2, tl, m) + get(x, l, r, v * 2 + 1, m + 1, tr);
}

bool check(int x, int l, int r){
    if(get(x, l, r) >= x) return 1;
    else return 0;
}
 
signed main(){
   	speed;
    int q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build();
    while(q--){
        int l, r;
        cin >> l >> r;
        int L = 1, R = n + 1;
        while(R - L > 1){
            int m = (L + R) / 2;
            if(check(m, l, r)) L = m;
            else R = m;
        }
        cout << L << '\n';
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50