답안 #446009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446009	2021-07-20T12:44:35 Z	grt	Index (COCI21_index)	C++17	60 / 110	2500 ms	26244 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) {
		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});
				}
			}
		}
		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";
	}
}

Subtask #1

20.0 / 20.0

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

Subtask #2

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5068 KB	Output is correct
2	Correct	7 ms	5068 KB	Output is correct
3	Correct	6 ms	5068 KB	Output is correct
4	Correct	7 ms	5068 KB	Output is correct
5	Correct	6 ms	5068 KB	Output is correct
6	Correct	6 ms	5068 KB	Output is correct
7	Correct	6 ms	5152 KB	Output is correct
8	Correct	6 ms	5068 KB	Output is correct
9	Correct	7 ms	5068 KB	Output is correct
10	Correct	8 ms	5068 KB	Output is correct
11	Correct	653 ms	10708 KB	Output is correct
12	Correct	635 ms	10576 KB	Output is correct
13	Correct	595 ms	10584 KB	Output is correct
14	Correct	615 ms	10564 KB	Output is correct
15	Correct	640 ms	10568 KB	Output is correct
16	Correct	629 ms	10564 KB	Output is correct
17	Correct	607 ms	10692 KB	Output is correct
18	Correct	602 ms	10564 KB	Output is correct
19	Correct	626 ms	10568 KB	Output is correct
20	Correct	646 ms	10640 KB	Output is correct

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5068 KB	Output is correct
2	Correct	7 ms	5068 KB	Output is correct
3	Correct	6 ms	5068 KB	Output is correct
4	Correct	7 ms	5068 KB	Output is correct
5	Correct	6 ms	5068 KB	Output is correct
6	Correct	6 ms	5068 KB	Output is correct
7	Correct	6 ms	5152 KB	Output is correct
8	Correct	6 ms	5068 KB	Output is correct
9	Correct	7 ms	5068 KB	Output is correct
10	Correct	8 ms	5068 KB	Output is correct
11	Correct	653 ms	10708 KB	Output is correct
12	Correct	635 ms	10576 KB	Output is correct
13	Correct	595 ms	10584 KB	Output is correct
14	Correct	615 ms	10564 KB	Output is correct
15	Correct	640 ms	10568 KB	Output is correct
16	Correct	629 ms	10564 KB	Output is correct
17	Correct	607 ms	10692 KB	Output is correct
18	Correct	602 ms	10564 KB	Output is correct
19	Correct	626 ms	10568 KB	Output is correct
20	Correct	646 ms	10640 KB	Output is correct
21	Execution timed out	2567 ms	26244 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-