#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = (int) 5e5 + 5;
vector<int> t[4*MAXN];
void add(int v, int tl, int tr, int val, int pos){
if(tl == tr){
t[v].push_back(val);
}else{
int tm = (tl + tr) / 2;
if(pos <= tm){
add(2*v, tl, tm, val, pos);
}else{
add(2*v+1, tm + 1, tr, val, pos);
}
t[v].push_back(val);
}
}
int que(int v, int tl, int tr, int l, int r, int val){
if(l > r) return 0;
if(tl == l && tr == r){
return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
}else{
int tm = (tl + tr) / 2;
return que(2*v, tl, tm, l, min(tm, r), val) + que(2*v+1, tm + 1, tr, max(tm + 1, l), r, val);
}
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < N; i++){
add(1, 1, N, B[i], A[i]);
}
for(int i = 1; i < 4*MAXN; i++) sort(t[i].begin(), t[i].end());
}
int dp[MAXN];
int can(int M, int K[]) {
int N = n;
sort(K, K + M);
vector<int> lst;
dp[0] = que(1, 1, N , 1, K[0], K[0]) - K[0];
if(dp[0] < 0) return 0;
lst.push_back(0);
for(int i = 1; i < M; i++){
dp[i] = que(1, 1, N, 1, K[i], K[i]) - K[i];
while(lst.size() > 1){
int cur = lst.back();
lst.pop_back();
int deg1 = dp[cur] + que(1, 1, N, K[cur] + 1, K[i], K[i]);
int deg2 = dp[lst.back()] + que(1, 1, N , K[lst.back()] + 1, K[i], K[i]);
if(deg2 > deg1){
lst.push_back(cur);
break;
}
}
dp[i] = min(dp[i], dp[lst.back()] + que(1, 1, N, K[lst.back()] + 1, K[i], K[i]) - K[i]);
lst.push_back(i);
if(dp[i] < 0) return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'int que(int, int, int, int, int, int)':
teams.cpp:26:21: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
26 | return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
47232 KB |
Output is correct |
2 |
Correct |
35 ms |
47232 KB |
Output is correct |
3 |
Correct |
35 ms |
47352 KB |
Output is correct |
4 |
Correct |
35 ms |
47232 KB |
Output is correct |
5 |
Correct |
35 ms |
47352 KB |
Output is correct |
6 |
Correct |
36 ms |
47352 KB |
Output is correct |
7 |
Correct |
36 ms |
47352 KB |
Output is correct |
8 |
Correct |
36 ms |
47360 KB |
Output is correct |
9 |
Correct |
35 ms |
47348 KB |
Output is correct |
10 |
Correct |
35 ms |
47232 KB |
Output is correct |
11 |
Correct |
35 ms |
47348 KB |
Output is correct |
12 |
Correct |
36 ms |
47360 KB |
Output is correct |
13 |
Correct |
36 ms |
47360 KB |
Output is correct |
14 |
Correct |
36 ms |
47360 KB |
Output is correct |
15 |
Correct |
36 ms |
47360 KB |
Output is correct |
16 |
Correct |
36 ms |
47232 KB |
Output is correct |
17 |
Correct |
36 ms |
47224 KB |
Output is correct |
18 |
Correct |
36 ms |
47232 KB |
Output is correct |
19 |
Correct |
36 ms |
47232 KB |
Output is correct |
20 |
Correct |
36 ms |
47336 KB |
Output is correct |
21 |
Correct |
35 ms |
47232 KB |
Output is correct |
22 |
Correct |
35 ms |
47312 KB |
Output is correct |
23 |
Correct |
36 ms |
47232 KB |
Output is correct |
24 |
Correct |
36 ms |
47340 KB |
Output is correct |
25 |
Correct |
36 ms |
47232 KB |
Output is correct |
26 |
Correct |
38 ms |
47224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
239 ms |
61032 KB |
Output is correct |
2 |
Correct |
249 ms |
61220 KB |
Output is correct |
3 |
Correct |
255 ms |
61244 KB |
Output is correct |
4 |
Correct |
247 ms |
61676 KB |
Output is correct |
5 |
Correct |
138 ms |
57020 KB |
Output is correct |
6 |
Correct |
138 ms |
57148 KB |
Output is correct |
7 |
Correct |
137 ms |
57140 KB |
Output is correct |
8 |
Correct |
139 ms |
57148 KB |
Output is correct |
9 |
Correct |
98 ms |
56592 KB |
Output is correct |
10 |
Correct |
93 ms |
56280 KB |
Output is correct |
11 |
Correct |
90 ms |
55944 KB |
Output is correct |
12 |
Correct |
91 ms |
56600 KB |
Output is correct |
13 |
Correct |
120 ms |
58196 KB |
Output is correct |
14 |
Correct |
166 ms |
58652 KB |
Output is correct |
15 |
Correct |
219 ms |
60904 KB |
Output is correct |
16 |
Correct |
213 ms |
60652 KB |
Output is correct |
17 |
Correct |
108 ms |
58336 KB |
Output is correct |
18 |
Correct |
108 ms |
58088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
243 ms |
61800 KB |
Output is correct |
2 |
Correct |
249 ms |
61800 KB |
Output is correct |
3 |
Correct |
393 ms |
65256 KB |
Output is correct |
4 |
Correct |
242 ms |
61848 KB |
Output is correct |
5 |
Correct |
245 ms |
57660 KB |
Output is correct |
6 |
Correct |
232 ms |
57660 KB |
Output is correct |
7 |
Correct |
147 ms |
57532 KB |
Output is correct |
8 |
Correct |
234 ms |
57672 KB |
Output is correct |
9 |
Correct |
98 ms |
57112 KB |
Output is correct |
10 |
Correct |
110 ms |
56640 KB |
Output is correct |
11 |
Correct |
115 ms |
56452 KB |
Output is correct |
12 |
Correct |
177 ms |
57152 KB |
Output is correct |
13 |
Correct |
320 ms |
59216 KB |
Output is correct |
14 |
Correct |
409 ms |
62816 KB |
Output is correct |
15 |
Correct |
286 ms |
61796 KB |
Output is correct |
16 |
Correct |
276 ms |
61676 KB |
Output is correct |
17 |
Correct |
178 ms |
58460 KB |
Output is correct |
18 |
Correct |
158 ms |
58712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1517 ms |
122080 KB |
Output is correct |
2 |
Correct |
1487 ms |
122328 KB |
Output is correct |
3 |
Correct |
1926 ms |
128880 KB |
Output is correct |
4 |
Correct |
1497 ms |
121944 KB |
Output is correct |
5 |
Correct |
925 ms |
100060 KB |
Output is correct |
6 |
Correct |
899 ms |
99928 KB |
Output is correct |
7 |
Correct |
673 ms |
100060 KB |
Output is correct |
8 |
Correct |
913 ms |
99892 KB |
Output is correct |
9 |
Correct |
394 ms |
98288 KB |
Output is correct |
10 |
Correct |
394 ms |
94468 KB |
Output is correct |
11 |
Correct |
443 ms |
95016 KB |
Output is correct |
12 |
Correct |
615 ms |
96300 KB |
Output is correct |
13 |
Correct |
1278 ms |
106400 KB |
Output is correct |
14 |
Correct |
2019 ms |
124284 KB |
Output is correct |
15 |
Correct |
1329 ms |
119496 KB |
Output is correct |
16 |
Incorrect |
1338 ms |
118584 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |