Submission #577322

#	Time	Username	Problem	Language	Result	Execution time	Memory
577322		jamielim	Index (COCI21_index)	C++14	60 / 110	2569 ms	57180 KiB

index

#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;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		if(s==e){
			v.pb(arr[s]);
		}else{
			l=new node(s,m);
			r=new node(m+1,e);
			int p1=0,p2=0;
			for(int i=s;i<=e;i++){
				if(p1==SZ(l->v)){
					v.pb((r->v)[p2++]);
				}else if(p2==SZ(r->v)){
					v.pb((l->v)[p1++]);
				}else{
					if((l->v)[p1]<(r->v)[p2]){
						v.pb((l->v)[p1++]);
					}else{
						v.pb((r->v)[p2++]);
					}
				}
			}
		}
	}
	int qry(int x,int y,int val){
		if(s>=x&&e<=y){
			int b=lower_bound(ALL(v),val)-v.begin();
			return SZ(v)-b;
		}
		if(y<=m)return l->qry(x,y,val);
		if(x>m)return r->qry(x,y,val);
		return l->qry(x,m,val)+r->qry(m+1,y,val);
	}
}*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;
			if(root->qry(l,r,mid)>=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:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
index.cpp:62:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  for(int i=0;i<n;i++)scanf("%d",&arr[i]);
      |                      ~~~~~^~~~~~~~~~~~~~
index.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d%d",&l,&r);l--;r--;
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50