oj.uz

Submission #1024051

# Submission time Handle Problem Language Result Execution time Memory
1024051 2024-07-15T10:48:09 Z kustizus Index (COCI21_index) C++17
110 / 110
 1428 ms 16004 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,fma,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5;
int n,q,block,a[N+5],ans[N+5],FT[N+5];
struct Node{
    int l,r,idx;
};
bool comp(Node a, Node b){
    if (a.l/block!=b.l/block) return a.l/block<b.l/block;
    return a.r<b.r;
};
void Update(int pos, int val){
    for (;pos<=N;pos+=pos&(-pos)) FT[pos]+=val;
}
int Get(int pos){
    int val=0;
    for (;pos;pos-=pos&(-pos)) val+=FT[pos];
    return val;
}
vector <Node> v;
void Solve(){
    cin>>n>>q;
    for (int i=1;i<=n;++i) cin>>a[i];
    for (int i=1;i<=q;++i){
        int l,r;
        cin>>l>>r;
        v.push_back({l,r,i});
    }
    block=sqrt(n);
    sort(v.begin(),v.end(),comp);
    int x=1,y=0;
    for (int i=0;i<q;++i){
        while (x<v[i].l){
            Update(a[x],-1);
            ++x;
        }
        while (x>v[i].l){
            --x;
            Update(a[x],1);
        }
        while (y<v[i].r){
            ++y;
            Update(a[y],1);
        }
        while (y>v[i].r){
            Update(a[y],-1);
            --y;
        }
        int left=1,right=y-x+1;
        while (left<right){
            int md=left+right>>1;
            if (Get(N)-Get(md)>=md+1) left=md+1;
            else right=md;
        }
        ans[v[i].idx]=left;
    }
    for (int i=1;i<=q;++i) cout<<ans[i]<<"\n";
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int t=1;
    // cin>>t;
    while (t--) Solve();
    cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
}

Compilation message

index.cpp: In function 'void Solve()':
index.cpp:55:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             int md=left+right>>1;
      |                    ~~~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4572 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4568 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4572 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4568 KB Output is correct
11 Correct 165 ms 7104 KB Output is correct
12 Correct 176 ms 7108 KB Output is correct
13 Correct 166 ms 7076 KB Output is correct
14 Correct 163 ms 7096 KB Output is correct
15 Correct 169 ms 7100 KB Output is correct
16 Correct 165 ms 6944 KB Output is correct
17 Correct 168 ms 7100 KB Output is correct
18 Correct 160 ms 7108 KB Output is correct
19 Correct 169 ms 7100 KB Output is correct
20 Correct 165 ms 7104 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4572 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4568 KB Output is correct
11 Correct 165 ms 7104 KB Output is correct
12 Correct 176 ms 7108 KB Output is correct
13 Correct 166 ms 7076 KB Output is correct
14 Correct 163 ms 7096 KB Output is correct
15 Correct 169 ms 7100 KB Output is correct
16 Correct 165 ms 6944 KB Output is correct
17 Correct 168 ms 7100 KB Output is correct
18 Correct 160 ms 7108 KB Output is correct
19 Correct 169 ms 7100 KB Output is correct
20 Correct 165 ms 7104 KB Output is correct
21 Correct 1428 ms 15792 KB Output is correct
22 Correct 1399 ms 14632 KB Output is correct
23 Correct 1416 ms 15256 KB Output is correct
24 Correct 1425 ms 15380 KB Output is correct
25 Correct 1381 ms 15792 KB Output is correct
26 Correct 1387 ms 14768 KB Output is correct
27 Correct 1387 ms 15892 KB Output is correct
28 Correct 1374 ms 15452 KB Output is correct
29 Correct 1386 ms 14692 KB Output is correct
30 Correct 1376 ms 16004 KB Output is correct