/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;
int n, q, a[N], res[N];
vector<array<int, 5>> Q;
vector<array<int, 3>> searchs[N];
deque<int> t[N];
void build(int l, int r, int k){
if(l == r){
t[k] = {0, a[l]};
return;
}
int m = (l+r)>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
merge(all(t[k<<1]), all(t[k<<1|1]), back_inserter(t[k]));
t[k].pop_front();
// cout << l << ' ' << r << ": ";
// for(int u: t[k]) cout << u << ' ';
// cout << '\n';
}
void add_bs(int l, int r, int ql, int qr, int k, int val, int idx){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
searchs[k].pb({val, idx, int(t[k].size())});
return;
}
int m = (l + r) >> 1;
add_bs(l, m, ql, qr, k<<1, val, idx);
add_bs(m+1, r, ql, qr, k<<1|1, val, idx);
}
void s(int k, int l, int r, vector<array<int, 3>> v){
if(v.empty() || r < l) return;
int m = (l + r) >> 1;
vector<array<int, 3>> s_l, s_r;
for(auto u: v){
int val = u[0], idx = u[1];
if(val <= t[k][m]){
res[idx] -= t[k].size() - u[2];
res[idx] += t[k].size() - m;
u[2] = m;
// cout << u[0] << ' ' << u[1] << ':' << m << '\n';
s_l.pb(u);
}else{
s_r.pb(u);
}
}
s(k, l, m - 1, s_l);
s(k, m + 1, r, s_r);
}
void proc(){
for(int k = 1; k <= 4*n; ++k){
if(searchs[k].empty()) continue;
s(k, 0, t[k].size() - 1, searchs[k]);
searchs[k].clear();
}
}
void solve(){
cin >> n >> q;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 0; i < q; ++i){
int l, r; cin >> l >> r;
Q.pb({l, r, 1, r - l + 1, 0});
}
build(1, n, 1);
bool ok = 1;
while(ok){
ok = 0;
for(int i = 0; i < q; ++i){
if(Q[i][2] <= Q[i][3]){
res[i] = 0;
int m = (Q[i][2] + Q[i][3]) >> 1;
add_bs(1, n, Q[i][0], Q[i][1], 1, m, i);
ok = 1;
}
}
if(!ok) break;
proc();
for(int i = 0; i < q; ++i){
if(Q[i][2] <= Q[i][3]){
// cout << res[i] << ' ' << Q[i][2] << ' ' << Q[i][3] << '\n';
int m = (Q[i][2] + Q[i][3]) >> 1;
if(res[i] >= m){
Q[i][4] = m;
Q[i][2] = m + 1;
}else{
Q[i][3] = m - 1;
}
}
}
cout << '\n';
}
for(int i = 0; i < q; ++i) cout << Q[i][4] << '\n';
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int T = 1, aa;
// cin >> T;aa=T;
while(T--){
// cout << "Case #" << aa-T << ": ";
solve();
cout << '\n';
}
return 0;
}
Compilation message
index.cpp: In function 'int main()':
index.cpp:121:16: warning: unused variable 'aa' [-Wunused-variable]
121 | int T = 1, aa;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
256 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
256 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
256 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |