#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<pair<int,int>,int>
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t[N],tree[N],n,q,x,ans[N];
vector<int> c[N];
vector<pair<int,int> > st[N];
void upd(int ind,int val) {
for(ind;ind<=x;ind+=(-ind)&ind) {
tree[ind] += val;
}
}
int get(int ind) {
int ans = 0;
for(ind;ind>=1;ind-=(-ind)&ind) ans += tree[ind];
return ans;
}
void solve(int l,int r,vector<pii> v) {
if(l==r) {//cout<<l<<":))"<<" "<<get(r) - get(l)<<endl;
for(int i=0;i<c[l].size();i++) {
upd(c[l][i],1);
}
for(int i=0;i<v.size();i++) {
int L = v[i].f.f, r = v[i].f.s;
if(get(r) - get(L-1) >=l ) ans[v[i].s] = l;
}
for(int i=0;i<c[l].size();i++) {
upd(c[l][i],-1);
}
return ;
}
int mid = (l+r)/2;
for(int i=mid; i<=r; i++) {
for(int j=0;j<c[i].size();j++) {
upd(c[i][j],1);
}
}
vector<pii> x,y;
for(int i=0;i<v.size();i++) {
int l = v[i].f.f, r = v[i].f.s;
if(get(r) - get(l-1) >=mid ) {
ans[v[i].s] = mid;
x.push_back(v[i]);
}
else y.push_back(v[i]);
}
solve(l,mid-1,y);
for(int i=mid; i<=r; i++) {
for(int j=0;j<c[i].size();j++) {
upd(c[i][j],-1);
}
}
solve(mid+1,r,x);
}
main(){
cin>>n>>q;
x = 0;
for(int i=1;i<=n;i++){
int a;
cin>>a;
c[a].push_back(i);
x = max(x,a);
}
vector<pii> all;
for(int i=1;i<=q;i++) {
int l,r;
cin >> l >> r;
all.push_back({{l,r},i});
st[l].push_back({r,i});
}
solve(1,x,all);
for(int i=1;i<=q;i++) cout<<ans[i]<<" ";
}
Compilation message
index.cpp: In function 'void upd(long long int, long long int)':
index.cpp:12:6: warning: statement has no effect [-Wunused-value]
12 | for(ind;ind<=x;ind+=(-ind)&ind) {
| ^~~
index.cpp: In function 'long long int get(long long int)':
index.cpp:18:6: warning: statement has no effect [-Wunused-value]
18 | for(ind;ind>=1;ind-=(-ind)&ind) ans += tree[ind];
| ^~~
index.cpp: In function 'void solve(long long int, long long int, std::vector<std::pair<std::pair<long long int, long long int>, long long int> >)':
index.cpp:23:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<c[l].size();i++) {
| ~^~~~~~~~~~~~
index.cpp:26:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=0;i<v.size();i++) {
| ~^~~~~~~~~
index.cpp:30:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0;i<c[l].size();i++) {
| ~^~~~~~~~~~~~
index.cpp:37:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j=0;j<c[i].size();j++) {
| ~^~~~~~~~~~~~
index.cpp:42:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<v.size();i++) {
| ~^~~~~~~~~
index.cpp:52:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int j=0;j<c[i].size();j++) {
| ~^~~~~~~~~~~~
index.cpp: At global scope:
index.cpp:58:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
317 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
317 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
317 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
