oj.uz

Submission #577336

# Submission time Handle Problem Language Result Execution time Memory
577336 2022-06-14T14:45:14 Z jamielim Index (COCI21_index) C++14
0 / 110
 4 ms 724 KB 
#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

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--;
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -