제출 #1125033

#제출 시각아이디문제언어결과실행 시간메모리
1125033yavuzskarahanIndex (COCI21_index)C++20
110 / 110
1196 ms92536 KiB
// In the name of God, the Most Gracious, the Most Merciful. // @yavuzskarahan - iflbot(); #include <bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0); cin.tie(0); #define file(x) freopen(x ".in", "r", stdin); freopen(x ".out", "w", stdout); #define FOR(i, L, R) for (int i = (L); i <= (R); i++) #define SORT(v) sort((v).begin(), (v).end()) #define RSORT(v) sort((v).rbegin(), (v).rend()) #define int long long #define ll long long #define pb push_back #define ub(v, a) upper_bound((v).begin(), (v).end(), (a)) #define lb(v, a) lower_bound((v).begin(), (v).end(), (a)) #define f first #define s second #define tm (tl+(tr-tl)/2) #define space << " " << #define vi vector<int> #define pii pair<int,int> #define vpii vector<pair<int,int>> #define now chrono::high_resolution_clock::now() const long long N = 2e5+5; const long long M = 3e6+5; const long long SQRTN = sqrt(N); const long long MOD = 1e9+7; inline int sum(int a, int b) {return ((a%MOD)+(b%MOD))%MOD;} inline int mul(int a, int b) {return ((a%MOD)*(b%MOD))%MOD;} inline int epow(int n, int us){int cvp = 1; while(us){if (us%2){cvp *= n;}n *= n; us /= 2;} return cvp;} struct node{int l, r, val;}; int n, q, ptr; int a[N], root[N]; node sgt[32*N]; int update(int index, int tl, int tr, int pos){ sgt[++ptr] = sgt[index]; index = ptr; if (tl == tr) sgt[index].val++; else { if (pos <= tm) sgt[index].l = update(sgt[index].l, tl, tm, pos); else sgt[index].r = update(sgt[index].r, tm+1, tr, pos); sgt[index].val = sgt[sgt[index].l].val + sgt[sgt[index].r].val; } return index; } inline int query(int v, int u, int tl, int tr, int l, int r) { if (tr < l || tl > r) return 0; if (l <= tl && tr <= r) return sgt[v].val - sgt[u].val; return query(sgt[v].l, sgt[u].l, tl, tm, l, r) + query(sgt[v].r, sgt[u].r, tm+1, tr, l, r); } inline int solve() { cin >> n >> q; FOR(i,1,n) cin >> a[i]; root[0] = 0; FOR(i,1,n) root[i] = update(root[i-1], 1, 2e5, a[i]); while (q--) { int l, r; cin >> l >> r; int low = 1; int high = r-l+1; int h = 0; while (low <= high){ int mid = low+(high-low)/2; int cnt = query(root[r], root[l-1], 1, 2e5, mid, 2e5); if (cnt >= mid) {low = mid+1; h = mid;} else high = mid-1; } cout << h << endl; } return 0; } int32_t main() { #ifdef LOCAL auto start = now; #endif fast; int t = 1; //cin >> t; while(t--){ solve(); } #ifdef LOCAL auto end = now; chrono::duration<double> elapsed = end - start; cout << endl << "runtime: " << endl << elapsed.count() << endl; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...