oj.uz

Submission #1117363

# Submission time Handle Problem Language Result Execution time Memory
1117363 2024-11-23T12:04:23 Z Tai_xiu Index (COCI21_index) C++14
110 / 110
 1279 ms 193076 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=200005;
struct node
{
    Z l,r,val;
    node(){}
    node(Z _val,Z _l,Z _r){
    l=_l,r=_r,val=_val;}
}t[40*maxn];
Z n,q;
Z a[maxn],version[maxn];
Z cnode=0;
Z update(Z v,Z tl,Z tr,Z pos,Z nv)
{
    if (tl==tr){
        t[++cnode]=node(nv,0,0);
        return cnode;
    }
    Z curr=++cnode;
    Z tm=tl+tr>>1;
    if (pos<=tm){
        t[curr].l=update(t[v].l,tl,tm,pos,nv);
        t[curr].r=t[v].r;
    }
    else{
        t[curr].l=t[v].l;
        t[curr].r=update(t[v].r,tm+1,tr,pos,nv);
    }
    t[curr].val=t[t[curr].l].val+t[t[curr].r].val;
    return curr;
}
Z query(Z v,Z tl,Z tr,Z l,Z r)
{
    if (tl>tr || l>r || tl>r || tr<l) return 0;
    if (tl>=l && tr<=r) return t[v].val;
    Z tm=tl+tr>>1;
    return query(t[v].l,tl,tm,l,r)+query(t[v].r,tm+1,tr,l,r);
}
vi g[maxn];
void solve()
{
    cin>>n>>q;
    Z ma=0;
    FOR(i,1,n){ cin>>a[i]; ma=max(ma,a[i]);}
    FOR(i,1,n) g[a[i]+1].pb(i);
    FOR(i,1,n) version[1]=update(version[1],1,n,i,1);
  //  FOR(i,1,ma) cout<<version[i]<<" "<<'?'<<'\n';
    FOR(i,2,ma+1){
        version[i]=version[i-1];
        for (Z v:g[i]) version[i]=update(version[i],1,n,v,0);
    }
    while (q--){
        Z l,r;
        cin>>l>>r;
        Z l1=1,r1=ma;
        while (l1<=r1){
            Z mid=l1+r1>>1;
            if (query(version[mid],1,n,l,r)>=mid) l1=mid+1;
            else r1=mid-1;
        }
        cout<<l1-1<<'\n';
    }
  //  FOR(i,2,ma+1) cout<<query(version[i],1,n,1,n)<<'\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Z t=1;
  //  cin>>t;
    while(t--) solve();
}

Compilation message

index.cpp: In function 'long long int update(long long int, long long int, long long int, long long int, long long int)':
index.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     Z tm=tl+tr>>1;
      |          ~~^~~
index.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
index.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     Z tm=tl+tr>>1;
      |          ~~^~~
index.cpp: In function 'void solve()':
index.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |             Z mid=l1+r1>>1;
      |                   ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 3 ms 8784 KB Output is correct
3 Correct 4 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 4 ms 8784 KB Output is correct
6 Correct 4 ms 8784 KB Output is correct
7 Correct 3 ms 8956 KB Output is correct
8 Correct 3 ms 8784 KB Output is correct
9 Correct 3 ms 8784 KB Output is correct
10 Correct 3 ms 8812 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 3 ms 8784 KB Output is correct
3 Correct 4 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 4 ms 8784 KB Output is correct
6 Correct 4 ms 8784 KB Output is correct
7 Correct 3 ms 8956 KB Output is correct
8 Correct 3 ms 8784 KB Output is correct
9 Correct 3 ms 8784 KB Output is correct
10 Correct 3 ms 8812 KB Output is correct
11 Correct 186 ms 49492 KB Output is correct
12 Correct 191 ms 49660 KB Output is correct
13 Correct 173 ms 49480 KB Output is correct
14 Correct 171 ms 49464 KB Output is correct
15 Correct 173 ms 49480 KB Output is correct
16 Correct 168 ms 49480 KB Output is correct
17 Correct 171 ms 49576 KB Output is correct
18 Correct 167 ms 49480 KB Output is correct
19 Correct 188 ms 49488 KB Output is correct
20 Correct 169 ms 49484 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 3 ms 8784 KB Output is correct
3 Correct 4 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 4 ms 8784 KB Output is correct
6 Correct 4 ms 8784 KB Output is correct
7 Correct 3 ms 8956 KB Output is correct
8 Correct 3 ms 8784 KB Output is correct
9 Correct 3 ms 8784 KB Output is correct
10 Correct 3 ms 8812 KB Output is correct
11 Correct 186 ms 49492 KB Output is correct
12 Correct 191 ms 49660 KB Output is correct
13 Correct 173 ms 49480 KB Output is correct
14 Correct 171 ms 49464 KB Output is correct
15 Correct 173 ms 49480 KB Output is correct
16 Correct 168 ms 49480 KB Output is correct
17 Correct 171 ms 49576 KB Output is correct
18 Correct 167 ms 49480 KB Output is correct
19 Correct 188 ms 49488 KB Output is correct
20 Correct 169 ms 49484 KB Output is correct
21 Correct 1189 ms 192908 KB Output is correct
22 Correct 1156 ms 192884 KB Output is correct
23 Correct 1076 ms 192828 KB Output is correct
24 Correct 1070 ms 192796 KB Output is correct
25 Correct 1090 ms 192852 KB Output is correct
26 Correct 1251 ms 192812 KB Output is correct
27 Correct 1170 ms 192812 KB Output is correct
28 Correct 1176 ms 193076 KB Output is correct
29 Correct 1279 ms 192844 KB Output is correct
30 Correct 1191 ms 192916 KB Output is correct