#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <climits>
#include <random>
using namespace std;
#define ll long long
#define pb push_back
#define ull unsigned long long
#define F first
#define S second
#define all(v) v.begin(), v.end()
const int INF = INT_MAX;
const int block = 500;
int t[200005], n, q;
int a[200001], ans[200001];
void upd(int i, int x){
for(; i < 200005; i = (i | (i + 1)))
t[i] += x;
}
int get(int r){
int ret = 0;
for(; r >= 0; r = ((r & (r + 1)) - 1)){
ret += t[r];
}
return ret;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
if(a.F.F / block == b.F.F / block)
return a.F.S < b.F.S;
return ((a.F.F / block) < (b.F.F / block));
}
void solve(){
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
vector<pair<pair<int, int>, int>> query;
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
query.pb({{l, r}, i});
}
sort(all(query), cmp);
int l = 1, r = 0;
for(auto [p, i] : query){
auto [tl, tr] = p;
while(l > tl){
l--;
upd(a[l], 1);
}
while(r < tr){
r++;
upd(a[r], 1);
}
while(l < tl){
upd(a[l], -1);
l++;
}
while(r > tr){
upd(a[r], -1);
r--;
}
int L = 1, R = n + 1;
while(R - L > 1){
int mid = (L + R) / 2;
if(mid <= get(mid, n)) L = mid;
else R = mid;
}
ans[i] = L;
}
for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int xach = 1;
//cin >> xach;
while(xach--) solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2392 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2392 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
154 ms |
3528 KB |
Output is correct |
12 |
Correct |
150 ms |
3788 KB |
Output is correct |
13 |
Correct |
150 ms |
3648 KB |
Output is correct |
14 |
Correct |
151 ms |
3528 KB |
Output is correct |
15 |
Correct |
151 ms |
3524 KB |
Output is correct |
16 |
Correct |
148 ms |
3528 KB |
Output is correct |
17 |
Correct |
151 ms |
3532 KB |
Output is correct |
18 |
Correct |
153 ms |
3652 KB |
Output is correct |
19 |
Correct |
152 ms |
3528 KB |
Output is correct |
20 |
Correct |
154 ms |
3532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2392 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
154 ms |
3528 KB |
Output is correct |
12 |
Correct |
150 ms |
3788 KB |
Output is correct |
13 |
Correct |
150 ms |
3648 KB |
Output is correct |
14 |
Correct |
151 ms |
3528 KB |
Output is correct |
15 |
Correct |
151 ms |
3524 KB |
Output is correct |
16 |
Correct |
148 ms |
3528 KB |
Output is correct |
17 |
Correct |
151 ms |
3532 KB |
Output is correct |
18 |
Correct |
153 ms |
3652 KB |
Output is correct |
19 |
Correct |
152 ms |
3528 KB |
Output is correct |
20 |
Correct |
154 ms |
3532 KB |
Output is correct |
21 |
Correct |
810 ms |
6296 KB |
Output is correct |
22 |
Correct |
820 ms |
6292 KB |
Output is correct |
23 |
Correct |
810 ms |
6340 KB |
Output is correct |
24 |
Correct |
827 ms |
6352 KB |
Output is correct |
25 |
Correct |
810 ms |
6352 KB |
Output is correct |
26 |
Correct |
811 ms |
6292 KB |
Output is correct |
27 |
Correct |
811 ms |
6608 KB |
Output is correct |
28 |
Correct |
816 ms |
6480 KB |
Output is correct |
29 |
Correct |
827 ms |
6436 KB |
Output is correct |
30 |
Correct |
826 ms |
6976 KB |
Output is correct |