| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577346 |
2022-06-14T14:55:30 Z |
jamielim |
Index (COCI21_index) |
C++14 |
|
3 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);
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
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--;
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
