#include "teams.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int MAXN = 5e5 + 12, BS = 300;
struct node{
int val = 0;
node *l = nullptr, *r = nullptr;
node(int _val = 0, node* _l = nullptr, node* _r = nullptr){
val = _val, l = _l, r = _r;
}
};
int getVal(node* v){
return v ? v->val: 0;
}
node* upd(node* v, int tl, int tr, int pos, int val){
if(tl == tr) return new node(getVal(v) + val);
int tm = (tl + tr) / 2;
if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v);
else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val));
v->val = getVal(v->l) + getVal(v->r);
return v;
}
int get(node* v, int tl, int tr, int l, int r){
if(tl > r || l > tr) return 0;
if(tl >= l && tr <= r) return getVal(v);
int tm = (tl + tr) / 2;
return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0);
}
node* root[MAXN];
int n, dp[MAXN];
vector< int > rv[MAXN], mine[MAXN];
void init(int N, int A[], int B[]) {
n = N, root[0] = new node();
for(int i = 0;i < n;i++)
rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]);
for(int i = 1;i <= n;i++){
root[i] = root[i - 1];
for(int v: rv[i]){
root[i] = upd(root[i], 1, n, v, 1);
}
}
}
int cf(int l, int r){
return get(root[n - r + 1], 1, n, l, r);
}
int can(int M, int K[]) {
sort(K, K + M);
vector< int > opt; int ptr = -1;
for(int i = 0;i < M;i++){
dp[i] = cf(1, K[i]) - K[i];
while(ptr >= 1 && dp[opt[ptr - 1]] + cf(K[opt[ptr - 1]] + 1, K[i]) < dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i])) opt.pop_back(), ptr--;
if(ptr >= 0) dp[i] = min(dp[i], dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i]) - K[i]);
ptr++, opt.push_back(i);
if(dp[i] < 0) return 0;
}
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
23776 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Correct |
14 ms |
23764 KB |
Output is correct |
4 |
Correct |
14 ms |
23812 KB |
Output is correct |
5 |
Correct |
14 ms |
23756 KB |
Output is correct |
6 |
Correct |
15 ms |
23884 KB |
Output is correct |
7 |
Correct |
14 ms |
23756 KB |
Output is correct |
8 |
Correct |
14 ms |
23820 KB |
Output is correct |
9 |
Correct |
14 ms |
23784 KB |
Output is correct |
10 |
Correct |
16 ms |
23756 KB |
Output is correct |
11 |
Correct |
13 ms |
23792 KB |
Output is correct |
12 |
Correct |
15 ms |
23756 KB |
Output is correct |
13 |
Correct |
14 ms |
23756 KB |
Output is correct |
14 |
Correct |
14 ms |
23792 KB |
Output is correct |
15 |
Correct |
14 ms |
23756 KB |
Output is correct |
16 |
Correct |
14 ms |
23812 KB |
Output is correct |
17 |
Correct |
14 ms |
23756 KB |
Output is correct |
18 |
Correct |
16 ms |
23756 KB |
Output is correct |
19 |
Correct |
15 ms |
23808 KB |
Output is correct |
20 |
Correct |
14 ms |
23708 KB |
Output is correct |
21 |
Correct |
14 ms |
23804 KB |
Output is correct |
22 |
Correct |
16 ms |
23764 KB |
Output is correct |
23 |
Correct |
14 ms |
23756 KB |
Output is correct |
24 |
Correct |
16 ms |
23804 KB |
Output is correct |
25 |
Correct |
15 ms |
23756 KB |
Output is correct |
26 |
Correct |
14 ms |
23756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
163 ms |
84280 KB |
Output is correct |
2 |
Correct |
162 ms |
84260 KB |
Output is correct |
3 |
Correct |
167 ms |
84240 KB |
Output is correct |
4 |
Correct |
192 ms |
84672 KB |
Output is correct |
5 |
Correct |
98 ms |
81860 KB |
Output is correct |
6 |
Correct |
99 ms |
81920 KB |
Output is correct |
7 |
Correct |
100 ms |
81840 KB |
Output is correct |
8 |
Correct |
109 ms |
81872 KB |
Output is correct |
9 |
Correct |
115 ms |
83136 KB |
Output is correct |
10 |
Correct |
103 ms |
82792 KB |
Output is correct |
11 |
Correct |
94 ms |
82488 KB |
Output is correct |
12 |
Correct |
94 ms |
82396 KB |
Output is correct |
13 |
Correct |
123 ms |
82248 KB |
Output is correct |
14 |
Correct |
121 ms |
83380 KB |
Output is correct |
15 |
Correct |
154 ms |
84016 KB |
Output is correct |
16 |
Correct |
147 ms |
84064 KB |
Output is correct |
17 |
Correct |
123 ms |
82604 KB |
Output is correct |
18 |
Correct |
102 ms |
82632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
165 ms |
84676 KB |
Output is correct |
2 |
Correct |
173 ms |
84668 KB |
Output is correct |
3 |
Correct |
255 ms |
87616 KB |
Output is correct |
4 |
Correct |
163 ms |
84676 KB |
Output is correct |
5 |
Correct |
154 ms |
82276 KB |
Output is correct |
6 |
Correct |
148 ms |
82244 KB |
Output is correct |
7 |
Correct |
106 ms |
82276 KB |
Output is correct |
8 |
Correct |
137 ms |
82260 KB |
Output is correct |
9 |
Correct |
125 ms |
83128 KB |
Output is correct |
10 |
Correct |
143 ms |
83040 KB |
Output is correct |
11 |
Correct |
145 ms |
82948 KB |
Output is correct |
12 |
Correct |
166 ms |
82764 KB |
Output is correct |
13 |
Correct |
226 ms |
82764 KB |
Output is correct |
14 |
Correct |
297 ms |
85828 KB |
Output is correct |
15 |
Correct |
195 ms |
84404 KB |
Output is correct |
16 |
Correct |
208 ms |
84548 KB |
Output is correct |
17 |
Correct |
151 ms |
83060 KB |
Output is correct |
18 |
Correct |
149 ms |
83044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1187 ms |
362820 KB |
Output is correct |
2 |
Correct |
1204 ms |
362816 KB |
Output is correct |
3 |
Correct |
1491 ms |
368532 KB |
Output is correct |
4 |
Correct |
1236 ms |
362692 KB |
Output is correct |
5 |
Correct |
629 ms |
350156 KB |
Output is correct |
6 |
Correct |
628 ms |
350128 KB |
Output is correct |
7 |
Correct |
522 ms |
350076 KB |
Output is correct |
8 |
Correct |
625 ms |
350052 KB |
Output is correct |
9 |
Correct |
586 ms |
351656 KB |
Output is correct |
10 |
Correct |
570 ms |
349724 KB |
Output is correct |
11 |
Correct |
582 ms |
349408 KB |
Output is correct |
12 |
Correct |
677 ms |
349452 KB |
Output is correct |
13 |
Correct |
1158 ms |
351080 KB |
Output is correct |
14 |
Correct |
1515 ms |
363292 KB |
Output is correct |
15 |
Correct |
1048 ms |
360024 KB |
Output is correct |
16 |
Incorrect |
1089 ms |
359860 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |