Submission #577336

#TimeUsernameProblemLanguageResultExecution timeMemory
577336jamielimIndex (COCI21_index)C++14
0 / 110
4 ms724 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; int n,q; int arr[200005]; struct node{ int s,e,m; vector<int> v; vector<int> vl,vr; node *l,*r; node(int S,int E){ s=S;e=E;m=(s+e)/2; if(s==e){ v.pb(arr[s]); vl.pb(0); vr.pb(0); }else{ l=new node(s,m); r=new node(m+1,e); vl.resize(e-s+1);vr.resize(e-s+1); int p1=0,p2=0,q1=0,q2=0; for(int i=s;i<=e;i++){ vl[i-s]=q1; vr[i-s]=q2; if(p1==SZ(l->v)){ v.pb((r->v)[p2++]); if(p2==SZ(r->v)||(r->v)[p2]!=(r->v)[p2-1])q2=p2; }else if(p2==SZ(r->v)){ v.pb((l->v)[p1++]); if(p1==SZ(l->v)||(l->v)[p1]!=(l->v)[p1-1])q1=p1; }else{ if((l->v)[p1]<(r->v)[p2]){ v.pb((l->v)[p1++]); if(p1==SZ(l->v)||(l->v)[p1]!=(l->v)[p1-1])q1=p1; }else{ v.pb((r->v)[p2++]); if(p2==SZ(r->v)||(r->v)[p2]!=(r->v)[p2-1])q2=p2; } } } } } int qry(int x,int y,int idx){ if(s>=x&&e<=y){ return SZ(v)-idx; } if(y<=m)return l->qry(x,y,vl[idx]); if(x>m)return r->qry(x,y,vr[idx]); return l->qry(x,m,vl[idx])+r->qry(m+1,y,vr[idx]); } }*root; int main(){ scanf("%d%d",&n,&q); for(int i=0;i<n;i++)scanf("%d",&arr[i]); root=new node(0,n-1); int l,r; while(q--){ scanf("%d%d",&l,&r);l--;r--; int mini=0,maxi=r-l+1; while(mini<maxi){ int mid=(mini+maxi+1)/2; int b=lower_bound(ALL(root->v),mid)-root->v.begin(); if(root->qry(l,r,b)>=mid){ // number of papers from l to r with >=mid citations mini=mid; }else{ maxi=mid-1; } } printf("%d\n",mini); } }

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
index.cpp:71:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  for(int i=0;i<n;i++)scanf("%d",&arr[i]);
      |                      ~~~~~^~~~~~~~~~~~~~
index.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d",&l,&r);l--;r--;
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...