Submission #943259

#	Time	Username	Problem	Language	Result	Execution time	Memory
943259		WeIlIaN	Index (COCI21_index)	C++17	60 / 110	2598 ms	42724 KiB

index

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()

#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;

vvi seg;
int n, q, t;

int cnt(int a, int b, int val, int cur, int l, int r) {
    if(b < l || a > r) {
        return 0;
    }
    if(a <= l && b >= r) {
        return seg[cur].size() - (lower_bound(all(seg[cur]), val)-seg[cur].begin());
    }
    int m = (l + r) / 2;
    return cnt(a, b, val, 2 * cur, l, m) + cnt(a, b, val, 2 * cur + 1, m + 1, r);
}



signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    t = 1;
    while(t < n) {
        t *= 2;
    }
    seg.resize(2 * t);
    vi arr(n);
    int x;
    REP(i, n) {
        cin>>arr[i];
        seg[i+t] = {arr[i]};
    }
    sort(all(arr));
    RFOR(i, 1, t) {
        seg[i].resize(seg[i*2].size() + seg[i*2+1].size());
        merge(all(seg[i*2]), all(seg[i*2+1]), seg[i].begin());
    }
    int a, b, left, right, mid;
    REP(i, q) {
        cin>>a>>b;
        left = 0, right = 200001;
        while(right - left > 1) {
            mid = (left + right) / 2;
            if(cnt(a, b, mid, 1, 1, t) >= mid) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        cout<<left<<endl;
    }
}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:80:9: warning: unused variable 'x' [-Wunused-variable]
   80 |     int x;
      |         ^

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