#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second
struct node{
int l;
int r;
int sum;
};
int nodecnt=0;
v<node> nodes;
int newNode(int l, int r){
int ndc = nodecnt++;
nodes.push_back(node());
nodes[ndc].l=l;
nodes[ndc].r=r;
nodes[ndc].sum = nodes[nodes[ndc].l].sum + nodes[nodes[ndc].r].sum;
return ndc;
}
int build(int l, int r){
if(l==r){
nodes.push_back(node());
nodes[nodecnt].l = -1;
nodes[nodecnt].r = -1;
nodes[nodecnt].sum=0;
return nodecnt++;
}
int m=(l+r)/2;
return newNode(build(l, m), build(m+1, r));
}
int update(int cur, int l, int r, int tar){
if(l==r) {
nodes.push_back(node());
nodes[nodecnt].l = -1;
nodes[nodecnt].r = -1;
nodes[nodecnt].sum=nodes[cur].sum+1;
return nodecnt++;
}
int m=(l+r)/2;
if(tar<=m){
return newNode(update(nodes[cur].l, l, m, tar), nodes[cur].r);
}
return newNode(nodes[cur].l, update(nodes[cur].r, m+1, r, tar));
}
int query(int cur, int l, int r, int ql){
if(ql<=l) return nodes[cur].sum;
int m=(l+r)/2, ret=0;
if(ql<=m) ret += query(nodes[cur].l, l, m, ql);
ret += query(nodes[cur].r, m+1, r, ql);
return ret;
}
int binSearchQuery(int curl, int curr, int l, int r, int num){
//returns last place where num<amount holds
if(l==r) return l;
int m=(l+r)/2;
int amount = nodes[nodes[curr].r].sum - nodes[nodes[curl].r].sum;
if(num >= amount) return binSearchQuery(nodes[curl].l, nodes[curr].l, l,m, num - amount);
return binSearchQuery(nodes[curl].r, nodes[curr].r, m+1, r, num);
}
int n;
ii points[500000];
v<int> roots;
int getRect(int x1, int x2, int y){
ii p1 = {x1, -1}, p2 = {x2+1, -1};
int ind1 = distance(points, lower_bound(points, points + n, p1));
int ind2 = distance(points, lower_bound(points, points + n, p2));
return query(roots[ind2], 1, n, y) - query(roots[ind1], 1, n, y);
}
int getSplit(int x1, int x2, int num){
ii p1 = {x1, -1}, p2 = {x2+1, -1};
int ind1 = distance(points, lower_bound(points, points + n, p1));
int ind2 = distance(points, lower_bound(points, points + n, p2));
return binSearchQuery(roots[ind1], roots[ind2], 1, n, num) + 1;//the first place where the suffix sum is >= num
}
void init(int N, int A[], int B[]) {
n=N;
for(int i=0; i<n; i++) {
points[i].fi=A[i];
points[i].se=B[i];
}
roots.push_back(build(1,n));
sort(points, points+n);
for(ii it:points) roots.push_back(update(roots.back(), 1, n, it.se));
}
int cnt=0;
int can(int M, int K[]) {
sort(K, K+M);
if(M>400){
priority_queue<ii> pq;
int j=0;
for(int i=0; i<M; i++){
while(j<n && points[j].fi<=K[i]){
pq.push({-points[j].se, points[j].fi});
j++;
}
while(pq.size()>0 && -pq.top().fi<K[i]) pq.pop();
if(pq.size()<K[i]) return 0;
for(int k=0; k<K[i]; k++) pq.pop();
}
return 1;
}
v<int> dp(M);
set<int> opt;
v<v<ii>> pq(M+1);
dp[0] = getRect(0, K[0], K[0]) - K[0];
opt.insert(0);
if(dp[0]<0) return 0;
for(int i=1; i<M; i++){
dp[i] = getRect(0, K[i], K[i]) - K[i];
for(ii it:pq[i]){
int j1=it.fi;
int j2=it.se;
if(opt.find(j1)==opt.end() || opt.find(j2)==opt.end()) continue;
opt.erase(j2);
}
auto it=opt.end();
it--;
int j=*it;
for(j=max(0,*it-2); j<min(i,*it+3); j++)
dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]);
if(dp[i]<0) return 0;
it = opt.end();
it--;
int j1=*it;
int j2=i;
int k = (K[j1]==K[j2]) ? 0 : getSplit(K[j1]+1, K[j2], dp[j2]-dp[j1]);
if(K[j1]==K[j2]) k= (dp[j2] - dp[j1] < 0) ? K[M-1]+1 : K[j2]+1;
auto it2 = lower_bound(K, K+M, k);
int l = distance(K, it2);
pq[l].push_back({j1,j2});
if(l>i) opt.insert(i);
}
return 1;
}
Compilation message
teams.cpp: In function 'int getRect(int, int, int)':
teams.cpp:71:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
71 | int ind1 = distance(points, lower_bound(points, points + n, p1));
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:72:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
72 | int ind2 = distance(points, lower_bound(points, points + n, p2));
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int getSplit(int, int, int)':
teams.cpp:77:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
77 | int ind1 = distance(points, lower_bound(points, points + n, p1));
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:78:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
78 | int ind2 = distance(points, lower_bound(points, points + n, p2));
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
107 | if(pq.size()<K[i]) return 0;
| ~~~~~~~~~^~~~~
teams.cpp:144:19: warning: conversion from 'std::iterator_traits<int*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
144 | int l = distance(K, it2);
| ~~~~~~~~^~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
28384 KB |
Output is correct |
2 |
Correct |
35 ms |
27900 KB |
Output is correct |
3 |
Correct |
65 ms |
51540 KB |
Output is correct |
4 |
Correct |
65 ms |
51576 KB |
Output is correct |
5 |
Correct |
65 ms |
51636 KB |
Output is correct |
6 |
Correct |
63 ms |
51628 KB |
Output is correct |
7 |
Correct |
66 ms |
51584 KB |
Output is correct |
8 |
Correct |
67 ms |
51556 KB |
Output is correct |
9 |
Correct |
65 ms |
51552 KB |
Output is correct |
10 |
Correct |
73 ms |
51568 KB |
Output is correct |
11 |
Correct |
65 ms |
51596 KB |
Output is correct |
12 |
Correct |
67 ms |
51536 KB |
Output is correct |
13 |
Correct |
65 ms |
51540 KB |
Output is correct |
14 |
Correct |
66 ms |
51552 KB |
Output is correct |
15 |
Correct |
66 ms |
51604 KB |
Output is correct |
16 |
Correct |
66 ms |
51624 KB |
Output is correct |
17 |
Correct |
55 ms |
52924 KB |
Output is correct |
18 |
Correct |
53 ms |
52960 KB |
Output is correct |
19 |
Correct |
59 ms |
53020 KB |
Output is correct |
20 |
Correct |
57 ms |
52916 KB |
Output is correct |
21 |
Correct |
55 ms |
52940 KB |
Output is correct |
22 |
Correct |
53 ms |
52968 KB |
Output is correct |
23 |
Correct |
55 ms |
52996 KB |
Output is correct |
24 |
Correct |
52 ms |
52876 KB |
Output is correct |
25 |
Correct |
52 ms |
52968 KB |
Output is correct |
26 |
Correct |
64 ms |
52888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
216 ms |
203876 KB |
Output is correct |
2 |
Correct |
207 ms |
203792 KB |
Output is correct |
3 |
Correct |
207 ms |
203804 KB |
Output is correct |
4 |
Correct |
219 ms |
204000 KB |
Output is correct |
5 |
Correct |
198 ms |
203468 KB |
Output is correct |
6 |
Correct |
190 ms |
203436 KB |
Output is correct |
7 |
Correct |
192 ms |
203500 KB |
Output is correct |
8 |
Correct |
194 ms |
203460 KB |
Output is correct |
9 |
Correct |
193 ms |
203532 KB |
Output is correct |
10 |
Correct |
191 ms |
203248 KB |
Output is correct |
11 |
Correct |
185 ms |
203244 KB |
Output is correct |
12 |
Correct |
189 ms |
203420 KB |
Output is correct |
13 |
Correct |
191 ms |
203596 KB |
Output is correct |
14 |
Correct |
200 ms |
203716 KB |
Output is correct |
15 |
Correct |
232 ms |
203836 KB |
Output is correct |
16 |
Correct |
208 ms |
203792 KB |
Output is correct |
17 |
Correct |
195 ms |
203928 KB |
Output is correct |
18 |
Correct |
196 ms |
203740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
211 ms |
204016 KB |
Output is correct |
2 |
Correct |
222 ms |
204080 KB |
Output is correct |
3 |
Correct |
308 ms |
204068 KB |
Output is correct |
4 |
Correct |
223 ms |
204044 KB |
Output is correct |
5 |
Correct |
636 ms |
203760 KB |
Output is correct |
6 |
Correct |
480 ms |
203628 KB |
Output is correct |
7 |
Correct |
191 ms |
203700 KB |
Output is correct |
8 |
Correct |
426 ms |
203744 KB |
Output is correct |
9 |
Correct |
186 ms |
203500 KB |
Output is correct |
10 |
Correct |
204 ms |
203340 KB |
Output is correct |
11 |
Correct |
373 ms |
203372 KB |
Output is correct |
12 |
Correct |
304 ms |
203512 KB |
Output is correct |
13 |
Correct |
352 ms |
203812 KB |
Output is correct |
14 |
Correct |
354 ms |
203912 KB |
Output is correct |
15 |
Correct |
270 ms |
203920 KB |
Output is correct |
16 |
Correct |
277 ms |
204004 KB |
Output is correct |
17 |
Correct |
262 ms |
203872 KB |
Output is correct |
18 |
Correct |
253 ms |
203916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
488 ms |
212312 KB |
Output is correct |
2 |
Correct |
516 ms |
212196 KB |
Output is correct |
3 |
Correct |
896 ms |
212268 KB |
Output is correct |
4 |
Correct |
505 ms |
212248 KB |
Output is correct |
5 |
Correct |
2369 ms |
211820 KB |
Output is correct |
6 |
Correct |
3942 ms |
211648 KB |
Output is correct |
7 |
Correct |
261 ms |
211440 KB |
Output is correct |
8 |
Correct |
2889 ms |
211436 KB |
Output is correct |
9 |
Correct |
252 ms |
211948 KB |
Output is correct |
10 |
Correct |
448 ms |
211284 KB |
Output is correct |
11 |
Correct |
2501 ms |
211348 KB |
Output is correct |
12 |
Correct |
518 ms |
211332 KB |
Output is correct |
13 |
Correct |
720 ms |
212812 KB |
Output is correct |
14 |
Correct |
1018 ms |
213712 KB |
Output is correct |
15 |
Correct |
626 ms |
213740 KB |
Output is correct |
16 |
Correct |
545 ms |
215232 KB |
Output is correct |
17 |
Correct |
398 ms |
214652 KB |
Output is correct |
18 |
Correct |
395 ms |
214580 KB |
Output is correct |