Submission #577346

#	Time	Username	Problem	Language	Result	Execution time	Memory
577346		jamielim	Index (COCI21_index)	C++14	0 / 110	3 ms	724 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;
	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);
			int p1=0,p2=0;
			for(int i=s;i<=e;i++){
				if(p1==SZ(l->v)){
					if(!v.empty()&&(r->v)[p2]==v.back()){
						vl.pb(vl.back());
						vr.pb(vr.back());
					}else{
						vl.pb(p1);
						vr.pb(p2);
					}
					v.pb((r->v)[p2++]);
				}else if(p2==SZ(r->v)){
					if(!v.empty()&&(l->v)[p1]==v.back()){
						vl.pb(vl.back());
						vr.pb(vr.back());
					}else{
						vl.pb(p1);
						vr.pb(p2);
					}
					v.pb((l->v)[p1++]);
				}else{
					if((l->v)[p1]<(r->v)[p2]){
						if(!v.empty()&&(l->v)[p1]==v.back()){
							vl.pb(vl.back());
							vr.pb(vr.back());
						}else{
							vl.pb(p1);
							vr.pb(p2);
						}
						v.pb((l->v)[p1++]);
					}else{
						if(!v.empty()&&(r->v)[p2]==v.back()){
							vl.pb(vl.back());
							vr.pb(vr.back());
						}else{
							vl.pb(p1);
							vr.pb(p2);
						}
						v.pb((r->v)[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:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
index.cpp:92:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  for(int i=0;i<n;i++)scanf("%d",&arr[i]);
      |                      ~~~~~^~~~~~~~~~~~~~
index.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d",&l,&r);l--;r--;
      |   ~~~~~^~~~~~~~~~~~~~

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