# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
422035 |
2021-06-09T15:32:21 Z |
Chaska |
Index (COCI21_index) |
C++11 |
|
2500 ms |
40580 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;
#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
#define fi first
#define sec second
#define mp make_pair
#define pb push_back
const int MAXN = 200005;
const int offset = (1 << 18);
struct tournament {
vector <int> v[offset * 2];
void insert(int a, int b) {
a += offset;
while (a) {
v[a].pb(b);
a /= 2;
}
}
void init() {
REP(i, offset * 2) {sort(all(v[i]));
if (v[i].size()>0) {
///cerr << i << " ";
///for (int u : v[i]) cerr << u << " ";
///cerr << "\n";
}}
}
int get(int cvor, int l, int r, int &a, int &b, int &x) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return (lower_bound(all(v[cvor]), x) - v[cvor].begin());
int mid = (l + r) / 2;
return get(cvor * 2, l, mid, a, b, x) + get(cvor * 2 + 1, mid + 1, r, a, b, x);
}
}T;
int n, q;
int main() {
scanf("%d %d",&n,&q);
REP(i, n) {
int x;
scanf("%d",&x);
T.insert(i, x);
}
T.init();
REP(t, q) {
int l, r;
scanf("%d %d",&l,&r);
l--; r--;
int lo = 1, hi = MAXN, mid;
while (lo != hi) {
mid = (lo + hi + 1) / 2;
int x = r - l + 1 - T.get(1, 0, offset - 1, l, r, mid);
if (x >= mid) lo = mid;
else hi = mid - 1;
}
printf("%d\n",lo);
}
return 0;
}
Compilation message
index.cpp: In function 'int main()':
index.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
index.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
index.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d %d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12740 KB |
Output is correct |
2 |
Correct |
15 ms |
12620 KB |
Output is correct |
3 |
Correct |
16 ms |
12664 KB |
Output is correct |
4 |
Correct |
15 ms |
12732 KB |
Output is correct |
5 |
Correct |
15 ms |
12620 KB |
Output is correct |
6 |
Correct |
15 ms |
12744 KB |
Output is correct |
7 |
Correct |
16 ms |
12736 KB |
Output is correct |
8 |
Correct |
15 ms |
12740 KB |
Output is correct |
9 |
Correct |
15 ms |
12740 KB |
Output is correct |
10 |
Correct |
15 ms |
12748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12740 KB |
Output is correct |
2 |
Correct |
15 ms |
12620 KB |
Output is correct |
3 |
Correct |
16 ms |
12664 KB |
Output is correct |
4 |
Correct |
15 ms |
12732 KB |
Output is correct |
5 |
Correct |
15 ms |
12620 KB |
Output is correct |
6 |
Correct |
15 ms |
12744 KB |
Output is correct |
7 |
Correct |
16 ms |
12736 KB |
Output is correct |
8 |
Correct |
15 ms |
12740 KB |
Output is correct |
9 |
Correct |
15 ms |
12740 KB |
Output is correct |
10 |
Correct |
15 ms |
12748 KB |
Output is correct |
11 |
Correct |
800 ms |
19708 KB |
Output is correct |
12 |
Correct |
862 ms |
19716 KB |
Output is correct |
13 |
Correct |
813 ms |
19728 KB |
Output is correct |
14 |
Correct |
797 ms |
19824 KB |
Output is correct |
15 |
Correct |
816 ms |
19856 KB |
Output is correct |
16 |
Correct |
799 ms |
19740 KB |
Output is correct |
17 |
Correct |
806 ms |
19876 KB |
Output is correct |
18 |
Correct |
842 ms |
19844 KB |
Output is correct |
19 |
Correct |
802 ms |
19676 KB |
Output is correct |
20 |
Correct |
798 ms |
19916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12740 KB |
Output is correct |
2 |
Correct |
15 ms |
12620 KB |
Output is correct |
3 |
Correct |
16 ms |
12664 KB |
Output is correct |
4 |
Correct |
15 ms |
12732 KB |
Output is correct |
5 |
Correct |
15 ms |
12620 KB |
Output is correct |
6 |
Correct |
15 ms |
12744 KB |
Output is correct |
7 |
Correct |
16 ms |
12736 KB |
Output is correct |
8 |
Correct |
15 ms |
12740 KB |
Output is correct |
9 |
Correct |
15 ms |
12740 KB |
Output is correct |
10 |
Correct |
15 ms |
12748 KB |
Output is correct |
11 |
Correct |
800 ms |
19708 KB |
Output is correct |
12 |
Correct |
862 ms |
19716 KB |
Output is correct |
13 |
Correct |
813 ms |
19728 KB |
Output is correct |
14 |
Correct |
797 ms |
19824 KB |
Output is correct |
15 |
Correct |
816 ms |
19856 KB |
Output is correct |
16 |
Correct |
799 ms |
19740 KB |
Output is correct |
17 |
Correct |
806 ms |
19876 KB |
Output is correct |
18 |
Correct |
842 ms |
19844 KB |
Output is correct |
19 |
Correct |
802 ms |
19676 KB |
Output is correct |
20 |
Correct |
798 ms |
19916 KB |
Output is correct |
21 |
Execution timed out |
2585 ms |
40580 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |