Submission #1071712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071712		Kevin_Jao	Index (COCI21_index)	C++14	110 / 110	2278 ms	48620 KiB

index

#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<utility>
#include<iomanip>
#include<string.h>
#include<limits.h>
#include<algorithm>
#include<functional>
#include<unordered_map> 
using namespace std;
#pragma GCC target("popcnt")
#define MOD 1000000007
// #define int long long
#define ss second
#define ff first
#define endl '\n'
const int mxN=2e5+1;
vector<int> a(mxN),v[4*mxN];
void merge(int node){
    int i=0,j=0;
    v[node].reserve(v[node*2].size()+v[node*2+1].size());
	while(i<v[node*2].size()||j<v[node*2+1].size()){
		if(j==v[node*2+1].size()||(i<v[node*2].size()&&v[node*2][i]<v[node*2+1][j])){
			v[node].push_back(v[node*2][i]);
			i++;
		}else{
            v[node].push_back(v[node*2+1][j]);  
			j++;
		}
	}
}
int sum(int node, int t){
    auto r=v[node].size();
    auto l=lower_bound(v[node].begin(),v[node].end(),t)-v[node].begin();
    return r-l;
}
void build(int node, int L, int R){
    if(L==R){
        v[node].push_back(a[L]);
        return;
    }
    build(node*2,L,(L+R)/2);
    build(node*2+1,(L+R)/2+1,R);
    merge(node);
}
int cal(int node, int L, int R, int l, int r, int d){
    if(L>r||R<l) return 0;
    if(L>=l&&R<=r) return sum(node,d);
    return cal(node*2,L,(L+R)/2,l,r,d)+cal(node*2+1,(L+R)/2+1,R,l,r,d);
}
void solve(){
    int n,q; cin>>n>>q;
    int mx=0;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    build(1,1,n);
    while(q--){
        int lt,rt; cin>>lt>>rt;
        int l=1,r=mx;
        while(l<=r){
            int m=l+(r-l)/2;
            if(cal(1,1,n,lt,rt,m)>=m){
                l=m+1;
            }else{
                r=m-1;
            }
        }
        cout<<l-1<<endl;
    }
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T=1;
    // cin>>T;
    while(T--){
        solve();
        cout<<endl;
    }
	return 0;
}

Compilation message (stderr)

index.cpp: In function 'void merge(int)':
index.cpp:31:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  while(i<v[node*2].size()||j<v[node*2+1].size()){
      |        ~^~~~~~~~~~~~~~~~~
index.cpp:31:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  while(i<v[node*2].size()||j<v[node*2+1].size()){
      |                            ~^~~~~~~~~~~~~~~~~~~
index.cpp:32:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if(j==v[node*2+1].size()||(i<v[node*2].size()&&v[node*2][i]<v[node*2+1][j])){
      |      ~^~~~~~~~~~~~~~~~~~~~
index.cpp:32:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if(j==v[node*2+1].size()||(i<v[node*2].size()&&v[node*2][i]<v[node*2+1][j])){
      |                              ~^~~~~~~~~~~~~~~~~

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