#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 500;
const int OFF = (1 << 18);
int n, q, t;
int niz[MAXN], rj[MAXN];
int iduci[MAXN];
vector<pair<pair<int, int>, int> > querys;
int ind, maks, koji[MAXN];
vector<pair<int, pair<int, int> > > v;
set<pair<int, pair<int, int> > > s;
vector<int> blokovi;
stack<int> stek;
int tour[2 * OFF];
void update (int x, int v) {
x += OFF;
tour[x] += v;
x /= 2;
while (x > 0) {
tour[x] = tour[2 * x] + tour[2 * x + 1];
x /= 2;
}
}
int query_ind (int k, int x = 1, int lo = 0, int hi = OFF) {
if (hi - lo == 1) return lo;
int mid = (lo + hi) / 2;
if (tour[2 * x] >= k) return query_ind(k, 2 * x, lo, mid);
else return query_ind (k - tour[2 * x], 2 * x + 1, mid, hi);
}
int query_sum (int a, int b, int x = 1, int lo = 0, int hi = OFF) {
if (a >= hi || b <= lo) return 0;
if (lo >= a && hi <= b) return tour[x];
int mid = (lo + hi) / 2;
return query_sum(a, b, 2 * x, lo, mid) + query_sum(a, b, 2 * x + 1, mid, hi);
}
void stavi (int l, int granica) {
while (l < granica) {
v.push_back ({niz[l], {l, min (iduci[l], granica - 1)}});
update (koji[l], min (iduci[l], granica - 1) - l + 1);
l = iduci[l] + 1;
}
}
void calc (int k, int vel) {
// cout << "AAA " << k << ' ' << vel << "\n";
if (vel == n / 2) {
for (int i = (int) v.size () - 1; i >= 0; i--) blokovi.push_back (v[i].second.first);
return;
}
// for (int i = OFF; i < OFF + 10; i++) cout << tour[i] << ' ';
// cout << "\n";
while (ind < querys.size () && min (querys[ind].first.first, maks) == k) {
int taj = querys[ind].first.second;
int bluk = query_ind (taj);
// cout << taj << ' ' << bluk << "\n";
// cout << blokovi[bluk] << ' ' << taj << ' ' << query_sum (0, bluk) << "\n";
rj[querys[ind].second] = niz[blokovi[bluk] + taj - query_sum(0, bluk) - 1];
ind++;
}
// for (auto it: v) cout << it.first << ' ' << it.second.first << ' ' << it.second.second << "\n";
maks = max (maks, k);
s.clear ();
for (auto it: v) s.insert (it);
while (true) {
auto it = s.end ();
it--;
if (vel - ((*it).second.second - (*it).second.first + 1) >= n / 2) {
blokovi.push_back((*it).second.first);
vel -= (*it).second.second - (*it).second.first + 1;
s.erase (it);
}
else break;
}
// cout << "AAAAAAAAAAa\n";
auto it = s.end ();
it--;
int l = (*it).second.first, r = (*it).second.second, mid = r - (vel - n / 2);
s.erase (it);
update (koji[l], -(r - l + 1));
v.clear ();
for (auto it: s) v.push_back(it);
v.push_back ({niz[l], {l, mid}});
update (koji[l], mid - l + 1);
stavi (mid + 1, r + 1);
calc (k + 1, vel);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie (0);
cout.tie (0);
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> niz[i];
for (int i = 0; i < n; i++) {
while (stek.size () > 0 && niz[i] > niz[stek.top ()]) {
iduci[stek.top ()] = i - 1;
stek.pop ();
}
stek.push(i);
}
while (stek.size () > 0) {
iduci[stek.top ()] = n - 1;
stek.pop ();
}
stavi (0, n / 2);
stavi (n / 2, n);
calc (1, n);
reverse (blokovi.begin (), blokovi.end ());
for (int i = 0; i < (int) blokovi.size (); i++) koji[blokovi[i]] = i;
for (int i = 0; i < q; i++) {
int t, a;
cin >> t >> a;
if (t > min (maks, 0)) querys.push_back ({{t,a}, i});
else rj[i] = niz[a - 1];
}
sort (querys.begin (), querys.end ());
// for (auto it: blokovi) cout << it << ' ';
// cout << "\n";
memset (tour, 0, sizeof (tour));
v.clear ();
stavi (0, n / 2);
stavi (n / 2, n);
calc (1, n);
for (int i = 0; i < q; i++) cout << rj[i] << "\n";
return 0;
}
Compilation message
Main.cpp: In function 'void calc(int, int)':
Main.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while (ind < querys.size () && min (querys[ind].first.first, maks) == k) {
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
23232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3092 ms |
7964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3026 ms |
7044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
23232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
