# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
446011 |
2021-07-20T12:52:30 Z |
grt |
Index (COCI21_index) |
C++17 |
|
697 ms |
19472 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
const int nax = 200 * 1000 + 10, INF = 1e9;
int n, q,mx;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];
int T[nax];
void add(int a, int x) {
while(a > 0) {
T[a] += x;
a -= (a & (-a));
}
}
int ask(int a) {
int w = 0;
while(a < mx) {
w += T[a];
a += (a & (-a));
}
return w;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> val[i];
mx = max(mx, val[i]);
}
for(int i = 1; i <= q; ++i) {
cin >> prz[i].ST >> prz[i].ND;
l[i] = 1; r[i] = prz[i].ND - prz[i].ST + 1;
mid[i] = (l[i] + r[i]) / 2;
contain[prz[i].ST - 1].PB(-i);
contain[prz[i].ND].PB(i);
}
for(int rep = 0; ; ++rep) {
for(int i = 0; i <= n; ++i) {
if(i > 0) {
add(val[i], 1);
}
for(auto x : contain[i]) {
if(x < 0) {
ans[-x] = -ask(mid[-x]);
} else {
ans[x] += ask(mid[x]);
}
}
}
for(int i = 1; i <= n; ++i) {
add(val[i], -1);
}
bool any = false;
for(int i = 1; i <= q; ++i) {
if(l[i] <= r[i]) {
if(ans[i] >= mid[i]) {
l[i] = mid[i] + 1;
} else {
r[i] = mid[i] - 1;
}
mid[i] = (l[i] + r[i]) / 2;
any = true;
}
}
if(!any) break;
}
for(int i = 1; i <= q; ++i) {
cout << l[i] - 1 << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5068 KB |
Output is correct |
2 |
Correct |
4 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
4 ms |
5068 KB |
Output is correct |
5 |
Correct |
4 ms |
5068 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
4 ms |
5068 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
4 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5068 KB |
Output is correct |
2 |
Correct |
4 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
4 ms |
5068 KB |
Output is correct |
5 |
Correct |
4 ms |
5068 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
4 ms |
5068 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
4 ms |
5068 KB |
Output is correct |
11 |
Correct |
119 ms |
7708 KB |
Output is correct |
12 |
Correct |
118 ms |
7704 KB |
Output is correct |
13 |
Correct |
111 ms |
7696 KB |
Output is correct |
14 |
Correct |
116 ms |
7688 KB |
Output is correct |
15 |
Correct |
114 ms |
7700 KB |
Output is correct |
16 |
Correct |
131 ms |
7816 KB |
Output is correct |
17 |
Correct |
115 ms |
7748 KB |
Output is correct |
18 |
Correct |
114 ms |
7748 KB |
Output is correct |
19 |
Correct |
140 ms |
7620 KB |
Output is correct |
20 |
Correct |
113 ms |
7688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5068 KB |
Output is correct |
2 |
Correct |
4 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
4 ms |
5068 KB |
Output is correct |
5 |
Correct |
4 ms |
5068 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
4 ms |
5068 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
4 ms |
5068 KB |
Output is correct |
11 |
Correct |
119 ms |
7708 KB |
Output is correct |
12 |
Correct |
118 ms |
7704 KB |
Output is correct |
13 |
Correct |
111 ms |
7696 KB |
Output is correct |
14 |
Correct |
116 ms |
7688 KB |
Output is correct |
15 |
Correct |
114 ms |
7700 KB |
Output is correct |
16 |
Correct |
131 ms |
7816 KB |
Output is correct |
17 |
Correct |
115 ms |
7748 KB |
Output is correct |
18 |
Correct |
114 ms |
7748 KB |
Output is correct |
19 |
Correct |
140 ms |
7620 KB |
Output is correct |
20 |
Correct |
113 ms |
7688 KB |
Output is correct |
21 |
Correct |
648 ms |
15664 KB |
Output is correct |
22 |
Correct |
675 ms |
19348 KB |
Output is correct |
23 |
Correct |
639 ms |
19380 KB |
Output is correct |
24 |
Correct |
646 ms |
19472 KB |
Output is correct |
25 |
Correct |
657 ms |
19404 KB |
Output is correct |
26 |
Correct |
697 ms |
19464 KB |
Output is correct |
27 |
Correct |
657 ms |
19396 KB |
Output is correct |
28 |
Correct |
624 ms |
19368 KB |
Output is correct |
29 |
Correct |
641 ms |
19364 KB |
Output is correct |
30 |
Correct |
659 ms |
19364 KB |
Output is correct |