답안 #446007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446007	2021-07-20T12:42:50 Z	grt	Index (COCI21_index)	C++17	60 / 110	2500 ms	29820 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 < 20; ++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	9 ms	5196 KB	Output is correct
2	Correct	10 ms	5168 KB	Output is correct
3	Correct	9 ms	5068 KB	Output is correct
4	Correct	10 ms	5068 KB	Output is correct
5	Correct	12 ms	5068 KB	Output is correct
6	Correct	10 ms	5168 KB	Output is correct
7	Correct	11 ms	5164 KB	Output is correct
8	Correct	10 ms	5068 KB	Output is correct
9	Correct	9 ms	5068 KB	Output is correct
10	Correct	9 ms	5164 KB	Output is correct

Subtask #2

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	5196 KB	Output is correct
2	Correct	10 ms	5168 KB	Output is correct
3	Correct	9 ms	5068 KB	Output is correct
4	Correct	10 ms	5068 KB	Output is correct
5	Correct	12 ms	5068 KB	Output is correct
6	Correct	10 ms	5168 KB	Output is correct
7	Correct	11 ms	5164 KB	Output is correct
8	Correct	10 ms	5068 KB	Output is correct
9	Correct	9 ms	5068 KB	Output is correct
10	Correct	9 ms	5164 KB	Output is correct
11	Correct	747 ms	11400 KB	Output is correct
12	Correct	689 ms	11388 KB	Output is correct
13	Correct	739 ms	11388 KB	Output is correct
14	Correct	686 ms	11308 KB	Output is correct
15	Correct	711 ms	11636 KB	Output is correct
16	Correct	751 ms	11384 KB	Output is correct
17	Correct	696 ms	11460 KB	Output is correct
18	Correct	701 ms	11384 KB	Output is correct
19	Correct	735 ms	11384 KB	Output is correct
20	Correct	713 ms	11380 KB	Output is correct

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	5196 KB	Output is correct
2	Correct	10 ms	5168 KB	Output is correct
3	Correct	9 ms	5068 KB	Output is correct
4	Correct	10 ms	5068 KB	Output is correct
5	Correct	12 ms	5068 KB	Output is correct
6	Correct	10 ms	5168 KB	Output is correct
7	Correct	11 ms	5164 KB	Output is correct
8	Correct	10 ms	5068 KB	Output is correct
9	Correct	9 ms	5068 KB	Output is correct
10	Correct	9 ms	5164 KB	Output is correct
11	Correct	747 ms	11400 KB	Output is correct
12	Correct	689 ms	11388 KB	Output is correct
13	Correct	739 ms	11388 KB	Output is correct
14	Correct	686 ms	11308 KB	Output is correct
15	Correct	711 ms	11636 KB	Output is correct
16	Correct	751 ms	11384 KB	Output is correct
17	Correct	696 ms	11460 KB	Output is correct
18	Correct	701 ms	11384 KB	Output is correct
19	Correct	735 ms	11384 KB	Output is correct
20	Correct	713 ms	11380 KB	Output is correct
21	Execution timed out	2552 ms	29820 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-