QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#709699 | #4780. 完美的队列 | NineSuns | 95 | 4714ms | 154524kb | C++14 | 4.0kb | 2024-11-04 16:18:58 | 2024-11-04 16:18:58 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5+5, B = N, b = 95, inf = 0x3f3f3f3f;
int n, m, a[N], l[N], r[N], x[N], rk[N], lb[B], rb[B], sr[N], cb[B], sa[N], bv[N], ans[N], ed;
pii stk[N];
vector <int> dx, col[N];
deque <pii> qs[N];
int mx, ad;
struct ST {
priority_queue <pii, vector <pii>, greater <pii> > a, b;
void ins (pii x) {
a.push(x);
}
void del (pii x) {
b.push(x);
}
int size () {
return 1l*a.size()-1l*b.size();
}
pii top () {
while (b.size() && a.top() == b.top()) a.pop(), b.pop();
return a.top();
}
}qb[B];
void chk (int id, int x, int k) {
if (l[id] <= lb[x] && rb[x] <= r[id]) {
mx += k; ad += k;
return;
}
if (l[id] > rb[x] || r[id] < lb[x]) return;
mx = -inf;
for (int j = max(l[id], lb[x]);j <= min(r[id], rb[x]);j++) bv[j] += k;
for (int j = lb[x];j <= rb[x];j++) mx = max(mx, ad+bv[j]);
}
void solve () {
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= m;i++) cin >> l[i] >> r[i] >> x[i], col[x[i]].pb(i);
for (int i = 1; ;i++) {
lb[i] = rb[i-1]+1; rb[i] = min(n, rb[i-1]+b);
for (int j = lb[i];j <= rb[i];j++) rk[j] = i;
if (rb[i] == n) break;
}
for (int i = 1;i <= m;i++) {
if (rk[l[i]] == rk[r[i]]) {
for (int j = l[i];j <= r[i];j++) {
sa[j]++;
if (qs[j].size()) {
qb[rk[j]].del({qs[j].front().fi-sa[j]+1, j});
if (sa[j]+cb[rk[j]] >= qs[j].front().fi) {
sr[qs[j].front().se] = max(sr[qs[j].front().se], i-1), qs[j].pop_front();
}
}
qs[j].pb({cb[rk[j]]+sa[j]+a[j], i});
qb[rk[j]].ins({qs[j].front().fi-sa[j], j});
}
}
else {
for (int j = l[i];j <= rb[rk[l[i]]];j++) {
sa[j]++;
if (qs[j].size()) {
qb[rk[j]].del({qs[j].front().fi-sa[j]+1, j});
if (sa[j]+cb[rk[j]] >= qs[j].front().fi) {
sr[qs[j].front().se] = max(sr[qs[j].front().se], i-1), qs[j].pop_front();
}
}
qs[j].pb({cb[rk[j]]+sa[j]+a[j], i});
qb[rk[j]].ins({qs[j].front().fi-sa[j], j});
}
for (int j = lb[rk[r[i]]];j <= r[i];j++) {
sa[j]++;
if (qs[j].size()) {
qb[rk[j]].del({qs[j].front().fi-sa[j]+1, j});
if (sa[j]+cb[rk[j]] >= qs[j].front().fi) {
sr[qs[j].front().se] = max(sr[qs[j].front().se], i-1), qs[j].pop_front();
}
}
qs[j].pb({cb[rk[j]]+sa[j]+a[j], i});
qb[rk[j]].ins({qs[j].front().fi-sa[j], j});
}
for (int j = rk[l[i]]+1;j < rk[r[i]];j++) {
cb[j]++;
while (qb[j].size()) {
pii k = qb[j].top();
if (k.fi > cb[j]) break;
qb[j].del(k);
sr[qs[k.se].front().se] = max(sr[qs[k.se].front().se], i-1);
qs[k.se].pop_front();
if (qs[k.se].size()) qb[j].ins({qs[k.se].front().fi-sa[k.se], k.se});
}
}
}
}
for (int i = 1;i <= n;i++) while (qs[i].size()) sr[qs[i].front().se] = m, qs[i].pop_front();
for (int i = 1;i <= rk[n];i++) {
dx.clear();
for (int j = 1;j <= m;j++) if (rk[l[j]] < i && i < rk[r[j]]) dx.pb(j);
int l = 1, r = 0; mx = -inf; ad = 0;
for (int z = lb[i];z <= rb[i];z++) mx = max(mx, a[z]), bv[z] = a[z];
for (int j : dx) {
while (r < j) ++r, chk(r, i, -1);
while (l <= j) chk(l, i, 1), l++;
while (r < m && mx > 0) ++r, chk(r, i, -1);
if (mx > 0) sr[j] = max(sr[j], m);
else sr[j] = max(sr[j], r-1);
}
}
for (int i = 1;i <= 1e5;i++) {
reverse(col[i].begin(), col[i].end());
for (int j : col[i]) {
int r = sr[j];
while (ed && stk[ed].fi <= r) {
r = max(r, stk[ed].se); ed--;
}
stk[++ed] = {j, r};
}
while (ed) {
ans[stk[ed].fi]++; ans[stk[ed].se+1]--;
ed--;
}
}
for (int i = 1;i <= m;i++) ans[i] += ans[i-1];
for (int i = 1;i <= m;i++) cout << ans[i] << '\n';
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while (T--) solve();
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 142ms
memory: 86504kb
input:
5000 4999 99 36 47 78 58 58 64 12 42 54 29 56 57 32 99 21 1 6 42 97 82 8 79 92 3 56 19 41 29 59 23 34 76 34 82 20 44 51 60 73 89 65 51 65 15 87 65 70 51 26 40 95 44 62 97 81 43 13 20 81 76 64 47 95 54 56 99 62 91 63 98 58 70 60 47 97 31 74 76 70 10 30 99 33 52 100 14 65 4 6 87 4 8 1 8 87 18 70 76 43...
output:
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 58 59 60 61 62 63 64 65 66 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
result:
ok 4999 numbers
Subtask #2:
score: 5
Accepted
Dependency #1:
100%
Accepted
Test #2:
score: 5
Accepted
time: 321ms
memory: 89452kb
input:
9999 10000 60 75 4 70 26 87 8 77 16 6 20 88 95 44 60 10 71 93 68 33 30 71 21 19 88 61 26 93 21 83 35 83 25 72 33 75 40 14 92 54 10 42 60 93 73 82 13 50 50 25 99 16 68 38 78 14 4 1 58 72 2 96 69 57 43 71 68 100 5 49 50 58 50 61 53 22 88 55 95 37 67 96 50 46 55 97 84 28 62 56 44 35 80 5 59 45 50 14 48...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 10000 numbers
Subtask #3:
score: 5
Accepted
Dependency #2:
100%
Accepted
Test #3:
score: 5
Accepted
time: 463ms
memory: 92848kb
input:
15000 15000 8 2 78 69 72 23 22 79 69 75 63 19 90 94 45 5 1 44 53 34 80 80 26 43 9 86 85 38 71 88 90 2 22 46 60 7 14 18 77 44 5 80 80 48 9 51 38 49 7 2 73 64 67 84 44 7 53 9 84 21 90 35 69 46 5 74 27 73 78 91 10 68 50 5 98 55 17 99 99 81 38 20 99 81 91 19 87 26 71 19 49 44 70 29 5 33 21 49 75 5 79 84...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 15000 numbers
Subtask #4:
score: 5
Accepted
Dependency #3:
100%
Accepted
Test #4:
score: 5
Accepted
time: 645ms
memory: 98796kb
input:
20000 20000 96 95 34 72 28 92 86 48 37 22 76 41 18 23 56 52 32 48 37 96 75 17 69 22 81 79 60 82 79 12 69 15 58 79 7 7 63 70 58 69 68 18 96 29 69 70 4 7 75 27 18 44 49 53 89 15 10 97 75 58 52 54 65 91 48 33 5 91 59 12 2 6 30 99 79 45 91 14 36 15 98 88 11 73 98 3 8 22 45 41 42 71 31 29 16 44 72 100 57...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 20000 numbers
Subtask #5:
score: 5
Accepted
Test #5:
score: 5
Accepted
time: 246ms
memory: 83464kb
input:
25000 25000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1 2 3 4 5 5 5 3 3 4 4 4 5 4 4 5 6 7 6 6 7 8 9 6 7 8 8 7 8 9 7 8 9 10 8 8 9 10 10 11 12 12 5 6 7 8 9 4 5 6 7 5 6 7 8 6 7 8 7 8 9 10 11 10 11 12 13 13 12 12 9 10 7 8 7 8 8 6 7 8 8 9 9 10 7 8 9 9 9 10 11 10 11 12 12 13 13 14 15 16 15 15 11 4 5 6 7 8 8 9 9 8 9 9 10 11 10 8 8 8 9 9 10 10 10 6 6 7 8 9 4 5...
result:
ok 25000 numbers
Subtask #6:
score: 5
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #6:
score: 5
Accepted
time: 1038ms
memory: 105208kb
input:
30000 30000 68 5 42 87 7 80 19 79 72 80 13 85 83 48 90 63 4 37 40 96 77 7 16 94 52 72 28 84 30 15 46 65 45 62 55 51 11 89 57 61 52 41 25 10 72 94 38 68 79 97 56 89 15 11 78 5 10 36 13 11 9 25 46 3 50 98 100 86 23 56 59 38 12 29 50 94 73 7 7 59 74 4 98 21 42 1 37 35 12 67 2 7 37 17 19 60 91 64 57 95 ...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 30000 numbers
Subtask #7:
score: 5
Accepted
Test #7:
score: 5
Accepted
time: 425ms
memory: 84936kb
input:
34999 35000 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 11 7 7 8 9 10 10 11 12 11 12 12 11 9 8 9 4 5 6 7 8 9 10 10 11 12 13 13 14 15 16 17 17 17 16 14 11 11 12 13 14 15 14 14 13 14 14 15 14 15 16 17 18 19 19 19 20 19 16 16 15 15 15 12 13 14 15 16 17 18 19 18 19 19 19 19 17 18 18 19 20 21 21 21 22 18 19 20 21 20 20 19 20 21 2...
result:
ok 35000 numbers
Subtask #8:
score: 5
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Test #8:
score: 5
Accepted
time: 1439ms
memory: 112888kb
input:
40000 40000 17 23 52 38 20 94 83 41 49 13 61 29 39 58 31 87 29 63 23 94 63 95 78 64 8 3 72 67 30 54 51 34 1 97 52 6 8 64 68 97 2 63 12 30 43 2 46 86 56 58 58 36 3 89 49 79 37 38 57 15 45 3 55 76 60 76 92 51 7 15 5 34 87 31 67 24 6 52 31 95 23 58 59 44 74 77 92 7 21 50 10 76 84 21 34 95 2 5 59 61 18 ...
output:
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 58 59 60 61 62 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 1...
result:
ok 40000 numbers
Subtask #9:
score: 5
Accepted
Test #9:
score: 5
Accepted
time: 751ms
memory: 85776kb
input:
45000 45000 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 18 19 20 21 22 23 24 24 25 26 27 28 29 29 30 31 30 31 32 31 31 32 32 33 34 34 35 36 37 38 38 39 39 39 38 38 39 40 41 40 41 42 40 40 41 42 43 43 44 45 46 47 48 44 45 44 45 46 45 44 44 45 45 46 47 48 47 48 49 50 51 52 51 52 51 51 50 50 51 52 52 52 52 52 53 ...
result:
ok 45000 numbers
Subtask #10:
score: 5
Accepted
Dependency #8:
100%
Accepted
Dependency #9:
100%
Accepted
Test #10:
score: 5
Accepted
time: 1935ms
memory: 120704kb
input:
50000 50000 93 35 69 99 23 3 93 39 95 53 2 59 1 25 67 8 73 72 65 33 60 11 96 99 40 56 88 72 32 60 48 49 42 63 75 50 35 80 34 46 38 54 71 36 81 52 46 32 19 54 10 20 36 29 4 83 93 3 72 21 37 1 30 48 32 99 91 65 12 27 13 81 11 59 22 89 90 6 30 15 62 91 8 2 38 98 57 77 62 93 86 17 95 97 73 11 16 2 28 87...
output:
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 58 59 60 61 62 63 64 65 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 1...
result:
ok 50000 numbers
Subtask #11:
score: 5
Accepted
Dependency #5:
100%
Accepted
Dependency #7:
100%
Accepted
Dependency #9:
100%
Accepted
Test #11:
score: 5
Accepted
time: 1137ms
memory: 86428kb
input:
54444 55000 3 5 10 6 4 10 10 6 2 10 5 2 6 9 10 6 5 9 3 4 7 6 9 1 1 2 6 10 5 2 6 3 10 3 4 7 3 3 3 5 9 2 2 8 6 10 6 9 1 1 3 2 6 8 9 3 10 4 10 5 6 5 7 6 9 4 7 4 10 8 5 10 1 5 8 4 4 5 9 3 9 3 2 1 2 7 5 10 3 4 6 10 4 8 6 9 6 6 6 8 8 3 3 2 9 9 7 3 8 9 4 4 3 5 10 5 10 6 7 2 10 1 1 10 6 1 6 3 7 1 8 7 9 4 5 ...
output:
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 32 33 33 33 32 33 34 35 36 37 38 38 39 38 37 38 39 40 40 40 41 42 43 44 45 46 46 47 48 48 49 50 51 50 51 51 52 53 54 55 54 53 53 52 53 54 52 53 52 51 52 52 53 54 55 52 53 54 53 54 54 54 55 56 56 56 55 55 56 55 54 ...
result:
ok 55000 numbers
Subtask #12:
score: 5
Accepted
Dependency #11:
100%
Accepted
Test #12:
score: 5
Accepted
time: 2448ms
memory: 127404kb
input:
60000 60000 55 3 74 22 46 71 40 1 41 52 27 48 31 19 84 36 89 45 7 36 91 41 79 43 43 64 58 6 80 80 66 52 60 58 47 84 31 11 74 43 74 23 79 31 45 17 85 49 53 96 45 92 59 30 30 15 59 63 52 47 17 10 72 91 8 29 1 74 86 100 91 13 85 77 79 34 10 83 76 54 52 63 5 76 45 62 80 47 21 46 36 12 9 93 28 50 86 43 9...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 60000 numbers
Subtask #13:
score: 5
Accepted
Test #13:
score: 5
Accepted
time: 1597ms
memory: 86840kb
input:
65000 65000 5 7 8 6 3 6 8 7 2 3 5 10 9 9 4 3 9 1 2 9 1 1 6 10 1 10 5 4 7 1 9 6 6 8 10 5 8 3 2 5 2 3 6 8 7 3 2 3 6 5 1 10 6 2 4 7 8 1 3 3 5 4 2 5 2 5 3 3 6 7 6 9 5 3 10 3 6 2 8 10 9 10 2 5 4 10 3 3 6 3 5 7 141 3 6 3 10 2 7 6 3 5 9 4 10 1 3 9 9 8 2 5 10 1 7 1 8 5 3 3 7 7 9 7 4 1 9 2 2 4 8 6 10 5 7 3 3...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 65000 numbers
Subtask #14:
score: 5
Accepted
Dependency #12:
100%
Accepted
Dependency #13:
100%
Accepted
Test #14:
score: 5
Accepted
time: 3031ms
memory: 135860kb
input:
70000 70000 54 42 81 48 90 100 68 36 70 5 93 14 38 37 27 29 66 51 92 69 40 74 70 59 69 85 38 24 24 83 53 66 58 69 26 5 31 19 34 19 92 31 80 65 39 22 61 44 18 84 69 4 28 81 60 16 54 90 10 44 63 100 52 10 65 14 28 42 25 46 89 82 67 92 61 15 40 87 72 49 31 57 52 71 16 27 28 33 96 11 75 12 35 1 23 93 80...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 70000 numbers
Subtask #15:
score: 5
Accepted
Dependency #13:
100%
Accepted
Test #15:
score: 5
Accepted
time: 1951ms
memory: 87380kb
input:
75000 75000 1 8 2 4 4 7 1 2 5 4 1 3 2 4 2 2 3 3 3 6 1 4 8 5 3 6 8 3 9 4 5 5 3 6 9 2 9 6 1 4 2 8 5 8 2 7 4 3 4 4 1 9 4 5 8 1 4 8 6 5 8 6 6 5 4 7 6 3 3 6 6 4 7 4 4 1 9 6 6 4 6 4 1 9 7 3 4 7 7 5 9 9 7 3 5 9 7 3 5 7 3 8 6 2 6 2 8 8 8 6 9 5 1 3 3 2 9 7 6 8 2 3 4 6 7 4 8 1 4 5 5 7 7 4 5 8 9 6 2 1225 7 9 6...
output:
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 1...
result:
ok 75000 numbers
Subtask #16:
score: 5
Accepted
Dependency #14:
100%
Accepted
Dependency #15:
100%
Accepted
Test #16:
score: 5
Accepted
time: 3623ms
memory: 143508kb
input:
80000 80000 36 90 42 28 58 80 90 68 41 93 51 46 31 59 94 62 17 48 63 27 64 83 69 43 81 1 4 32 98 57 38 56 83 21 6 95 29 63 44 88 74 45 75 75 51 45 89 33 37 50 3 11 1 69 66 87 12 44 11 90 4 66 17 97 37 21 89 11 84 71 53 60 11 63 34 86 99 61 60 79 37 24 50 15 2 88 11 16 79 36 70 89 81 41 55 51 18 99 8...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 80000 numbers
Subtask #17:
score: 5
Accepted
Dependency #16:
100%
Accepted
Test #17:
score: 5
Accepted
time: 3988ms
memory: 146868kb
input:
85000 85000 35 30 17 21 1 8 55 71 93 22 77 80 62 1 37 55 95 53 83 60 49 83 84 34 32 90 17 51 65 29 57 71 89 32 18 16 5 39 36 8 92 53 99 85 81 18 42 72 2 74 51 15 34 12 20 76 8 39 2 64 5 81 64 80 94 31 92 47 91 10 19 98 85 21 16 66 38 20 24 98 80 19 29 43 81 85 82 46 22 65 41 89 75 49 50 70 88 2 85 5...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 85000 numbers
Subtask #18:
score: 5
Accepted
Dependency #17:
100%
Accepted
Test #18:
score: 5
Accepted
time: 4368ms
memory: 150268kb
input:
90000 90000 81 45 45 33 1 89 77 35 65 10 35 12 63 23 72 87 69 19 55 63 29 36 84 42 44 46 58 3 15 35 41 29 81 85 21 81 3 91 81 77 75 23 26 95 26 65 62 62 22 15 53 54 76 100 26 47 66 49 71 10 22 47 29 67 10 70 77 48 14 35 39 44 29 84 57 61 97 26 12 59 98 10 51 11 67 77 10 17 37 90 4 99 45 89 37 95 26 ...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 90000 numbers
Subtask #19:
score: 5
Accepted
Dependency #18:
100%
Accepted
Test #19:
score: 5
Accepted
time: 4714ms
memory: 154524kb
input:
95000 95000 48 85 52 2 4 17 29 38 93 62 69 46 27 9 15 57 15 24 39 96 14 93 99 34 94 27 95 21 83 38 60 7 80 28 33 95 3 67 29 53 69 7 95 37 31 6 14 33 86 3 77 3 9 83 24 4 29 45 5 39 92 37 85 86 99 48 48 84 22 81 12 38 80 74 71 42 36 30 32 23 41 4 30 7 38 42 81 47 88 32 75 98 71 97 33 39 21 33 35 87 91...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 95000 numbers
Subtask #20:
score: 0
Time Limit Exceeded
Dependency #19:
100%
Accepted
Test #20:
score: 0
Time Limit Exceeded
input:
100000 100000 15 56 36 27 48 45 25 41 22 91 96 12 58 50 99 18 25 5 92 29 31 57 14 50 84 15 99 71 15 66 79 21 54 38 76 84 79 74 21 30 87 60 95 71 25 87 67 72 59 60 1 39 33 58 78 37 56 80 96 13 61 27 33 38 88 33 7 20 29 84 10 7 86 32 53 23 42 65 29 75 44 99 9 70 18 31 93 9 62 29 38 98 65 73 28 58 15 4...
output:
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...