Submission #1125013

#TimeUsernameProblemLanguageResultExecution timeMemory
1125013yavuzskarahanIndex (COCI21_index)C++20
0 / 110
17 ms19264 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 K = 23; 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;} int n, q, l, r, a[N]; vi sgt[4*N]; inline bool compare(const int& a, const int& b){ return a < b; } inline vi merge(const vi& a, const vi& b){ vi result(a.size()+b.size()); merge(a.begin(), a.end(), b.begin(), b.end(), result.begin(), compare); return result; } inline void build(int v, int tl, int tr) { if (tl == tr) {sgt[v].pb(a[tl]); return;} build(2*v, tl, tm); build(2*v+1, tm+1, tr); sgt[v] = merge(sgt[2*v], sgt[2*v+1]); } inline int query(int v, int tl, int tr, int l, int r, int mid) { if (tr < l || tl > r) return 0; if (l <= tl && tr <= r){ auto it = lb(sgt[v], mid); if ((*it) == mid) it--; return sgt[v].end() - it; // num of mid <= } return query(2*v, tl, tm, l, r, mid) + query(2*v+1, tm+1, tr, l, r, mid); } inline int h(int currl, int currr){ r = currr-currl+1; l = 1; int hIndex = 0; while(l<=r){ int m = l+(r-l)/2; if (query(1,1,n,currl,currr,m) >= m) {hIndex = m; l = m+1;} else r = m-1; } return hIndex; } inline int solve() { cin >> n >> q; FOR(i,1,n) cin >> a[i]; build(1,1,n); while (q--) { cin >> l >> r; cout << h(l,r) << 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...