Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)

B - Box

显然如果$q{i-1} < q{i}$(或$i=0$),则$p{i}=q{i}$,否则就将1~n里从小到大选择第一个没用过的数字当成$p{i}$. 每次检查一下最大值是否真正等于$q{i}$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;

vector<int> p, q;
vector<bool> used;
p.resize(n);
q.resize(n);
used.resize(n + 1);

bool ok = true;
for (int i = 0; i < n; i++)
{
cin >> q[i];
ok &= q[i] > i;
if (i == 0 || q[i] > q[i - 1])
{
p[i] = q[i];
used[p[i]] = true;
}
}
ok &= q[n - 1] == n;

int unused = 1, maxi = 0;
for (int i = 0; i < n && ok; i++)
{
if (!p[i])
{
while (used[unused])
unused++;
p[i] = unused;
used[unused] = true;
}
maxi = max(maxi, p[i]);
if (maxi != q[i])
ok = false;
}

if (ok)
{
for (int i = 0; i < n; i++)
cout << p[i] << ' ';
cout << endl;
}
else
cout << -1 << endl;
}
return 0;
}

D - Optimal Subsequences (Hard Version)

将输入数据降序排序,如果值相等则位置靠前的优先,并记录每个数的原位置。之后将查询离线。建立一棵BST(按照每个数的原位置排序),将排序好的数据依次插入BST中。且每插入一个数就处理k为当前BST中元素数目的查询。对于查询(k,pos),答案就是当前BST中第pos大的数。

由于STL里的set并没有查询第k大的功能,所以就需要用到pb_ds. (然而尝试用kotlin超时了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
constexpr int MAXN = 200000;
using namespace std;
int n, m, ans[MAXN + 5];
pair<int, int> a[MAXN + 5], b[MAXN + 5];
bool cmp1(const pair<int, int> a, const pair<int, int> b)
{
if (a.first == b.first)
return a.second < b.second;
else
return a.first > b.first;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + 1 + n, cmp1);

cin >> m;
unordered_map<int, unordered_map<int, vector<int>>> query;
for (int i = 1; i <= m; i++)
{
int k, pos;
cin >> k >> pos;
query[k][pos].push_back(i);
}

__gnu_pbds::tree<pair<int, int>, __gnu_pbds::null_type, less<pair<int, int>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> tr;
for (int i = 1; i <= n; i++)
{
tr.insert(make_pair(a[i].second, a[i].first));
for (auto p : query[i])
{
int res = tr.find_by_order(p.first - 1)->second;
for (auto q : query[i][p.first])
ans[q] = res;
}
}

for (int i = 1; i <= m; i++)
cout << ans[i] << endl;
return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/uncategorized/2019/11/Codeforces-Round-602-Div-2-based-on-Technocup-2020-Elimination-Round-3/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.