답안 #446008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446008	2021-07-20T12:43:33 Z	grt	Index (COCI21_index)	C++17	60 / 110	2500 ms	26116 KB

index

#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;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];
ordered_set S;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> 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 < 18; ++rep) {
		S.clear();
		int id = 1;
		for(int i = 0; i <= n; ++i) {
			if(i > 0) {
				S.insert({-val[i], id++});
			}
			for(auto x : contain[i]) {
				if(x < 0) {
					ans[-x] = -S.order_of_key({-mid[-x], INF});
				} else {
					ans[x] += S.order_of_key({-mid[x], INF});
				}
			}
		}
		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;
			}
		}
	}
	for(int i = 1; i <= q; ++i) {
		cout << l[i] - 1 << "\n";
	}
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5068 KB	Output is correct
2	Correct	8 ms	5052 KB	Output is correct
3	Correct	8 ms	5160 KB	Output is correct
4	Correct	9 ms	5128 KB	Output is correct
5	Correct	8 ms	5068 KB	Output is correct
6	Correct	10 ms	5068 KB	Output is correct
7	Correct	9 ms	5152 KB	Output is correct
8	Correct	9 ms	5160 KB	Output is correct
9	Correct	8 ms	5156 KB	Output is correct
10	Correct	9 ms	5068 KB	Output is correct

Subtask #2

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5068 KB	Output is correct
2	Correct	8 ms	5052 KB	Output is correct
3	Correct	8 ms	5160 KB	Output is correct
4	Correct	9 ms	5128 KB	Output is correct
5	Correct	8 ms	5068 KB	Output is correct
6	Correct	10 ms	5068 KB	Output is correct
7	Correct	9 ms	5152 KB	Output is correct
8	Correct	9 ms	5160 KB	Output is correct
9	Correct	8 ms	5156 KB	Output is correct
10	Correct	9 ms	5068 KB	Output is correct
11	Correct	672 ms	10572 KB	Output is correct
12	Correct	681 ms	10564 KB	Output is correct
13	Correct	682 ms	10568 KB	Output is correct
14	Correct	634 ms	10564 KB	Output is correct
15	Correct	674 ms	10568 KB	Output is correct
16	Correct	689 ms	10572 KB	Output is correct
17	Correct	640 ms	10564 KB	Output is correct
18	Correct	672 ms	10580 KB	Output is correct
19	Correct	706 ms	10568 KB	Output is correct
20	Correct	638 ms	10568 KB	Output is correct

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5068 KB	Output is correct
2	Correct	8 ms	5052 KB	Output is correct
3	Correct	8 ms	5160 KB	Output is correct
4	Correct	9 ms	5128 KB	Output is correct
5	Correct	8 ms	5068 KB	Output is correct
6	Correct	10 ms	5068 KB	Output is correct
7	Correct	9 ms	5152 KB	Output is correct
8	Correct	9 ms	5160 KB	Output is correct
9	Correct	8 ms	5156 KB	Output is correct
10	Correct	9 ms	5068 KB	Output is correct
11	Correct	672 ms	10572 KB	Output is correct
12	Correct	681 ms	10564 KB	Output is correct
13	Correct	682 ms	10568 KB	Output is correct
14	Correct	634 ms	10564 KB	Output is correct
15	Correct	674 ms	10568 KB	Output is correct
16	Correct	689 ms	10572 KB	Output is correct
17	Correct	640 ms	10564 KB	Output is correct
18	Correct	672 ms	10580 KB	Output is correct
19	Correct	706 ms	10568 KB	Output is correct
20	Correct	638 ms	10568 KB	Output is correct
21	Execution timed out	2566 ms	26116 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-