#include <bits/stdc++.h>
#include "teams.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5+10;
int n;
pii range[maxn];
int ind[maxn];
int opt[maxn];
struct Node
{
Node *l, *r;
int v;
Node()
{
l = r = NULL;
v = 0;
}
} *version[maxn];
struct PersistentSegmentTree
{
void build(Node *node, int l, int r)
{
if (l == r) return;
int mid = (l+r)>>1;
node->l = new Node(); node->r = new Node();
build(node->l, l, mid); build(node->r, mid+1, r);
}
void upd(Node *prev, Node *node, int l, int r, int pos, int v)
{
if (l == r)
{
node->v = prev->v + v;
return;
}
int mid = (l+r)>>1;
if (pos <= mid)
{
if (!node->l) node->l = new Node();
node->r = prev->r;
upd(prev->l, node->l, l, mid, pos, v);
}
else
{
if (!node->r) node->r = new Node();
node->l = prev->l;
upd(prev->r, node->r, mid+1, r, pos, v);
}
node->v = node->l->v + node->r->v;
}
int query(Node *prev, Node *node, int l, int r, int a, int b)
{
if (l > b || r < a) return 0;
if (l >= a && r <= b) return node->v - prev->v;
int mid = (l+r)>>1;
return query(prev->l, node->l, l, mid, a, b) + query(prev->r, node->r, mid+1, r, a, b);
}
int get(int l, int r, int k)
{
return query(version[ind[l]], version[ind[r]], 1, n, k, n);
}
} seg;
void init(int N, int A[], int B[])
{
n = N;
for (int i = 1; i <= n; i++)
range[i] = {A[i-1], B[i-1]};
sort(range+1, range+n+1);
int ptr = 1, aux = 0;
version[0] = new Node();
seg.build(version[0], 1, n);
for (int i = 1; i <= n; i++)
{
while (ptr <= n && range[ptr].ff == i)
{
version[++aux] = new Node();
seg.upd(version[aux-1], version[aux], 1, n, range[ptr].ss, 1);
ptr++;
}
ind[i] = aux;
}
}
ll dp[maxn];
int fq[maxn];
vector<int> V;
void solve(int l, int r)
{
if (l > r) return;
int mid = (l+r)>>1;
int k = V[mid];
dp[mid] = 1ll*seg.get(0, k, k) - 1ll*fq[k]*k;
opt[mid] = mid;
for (int i = 0; i < mid; i++)
{
ll x = dp[i] + 1ll*seg.get(V[i], k, k) - 1ll*fq[k]*k;
if (x < dp[mid])
dp[mid] = x, opt[mid] = i;
}
solve(l, mid-1); solve(mid+1, r);
}
int can(int M, int K[])
{
int m = M;
V.clear();
for (int i = 0; i < m; i++)
{
V.push_back(K[i]);
fq[K[i]]++;
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
m = V.size();
for (int i = 0; i < m; i++)
{
int k = V[i];
dp[i] = 1ll*seg.get(0, k, k) - 1ll*fq[k]*k;
opt[i] = i;
for (int j = (i == 0 ? 0 : opt[i-1]); j < i; j++)
{
ll x = dp[j] + 1ll*seg.get(V[j], k, k) - 1ll*fq[k]*k;
if (x <= dp[i]) dp[i] = x, opt[i] = j;
}
}
bool ok = 1;
for (int j = 0; j < m; j++)
{
if (dp[j] < 0) ok = 0;
dp[j] = fq[V[j]] = opt[j] = 0;
}
return ok;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:156:12: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
156 | m = V.size();
| ~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
64748 KB |
Output is correct |
2 |
Correct |
149 ms |
64780 KB |
Output is correct |
3 |
Correct |
149 ms |
64748 KB |
Output is correct |
4 |
Correct |
151 ms |
65768 KB |
Output is correct |
5 |
Correct |
109 ms |
64748 KB |
Output is correct |
6 |
Correct |
107 ms |
64748 KB |
Output is correct |
7 |
Correct |
108 ms |
64876 KB |
Output is correct |
8 |
Correct |
106 ms |
64748 KB |
Output is correct |
9 |
Correct |
95 ms |
63084 KB |
Output is correct |
10 |
Correct |
96 ms |
62828 KB |
Output is correct |
11 |
Correct |
105 ms |
65772 KB |
Output is correct |
12 |
Correct |
98 ms |
62644 KB |
Output is correct |
13 |
Correct |
113 ms |
65644 KB |
Output is correct |
14 |
Correct |
107 ms |
63340 KB |
Output is correct |
15 |
Correct |
144 ms |
64748 KB |
Output is correct |
16 |
Correct |
145 ms |
64748 KB |
Output is correct |
17 |
Correct |
107 ms |
65644 KB |
Output is correct |
18 |
Correct |
107 ms |
65644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
65132 KB |
Output is correct |
2 |
Correct |
219 ms |
65132 KB |
Output is correct |
3 |
Correct |
278 ms |
68588 KB |
Output is correct |
4 |
Correct |
152 ms |
65768 KB |
Output is correct |
5 |
Correct |
169 ms |
65260 KB |
Output is correct |
6 |
Correct |
163 ms |
65132 KB |
Output is correct |
7 |
Correct |
164 ms |
65132 KB |
Output is correct |
8 |
Correct |
163 ms |
65132 KB |
Output is correct |
9 |
Correct |
97 ms |
63084 KB |
Output is correct |
10 |
Correct |
99 ms |
63084 KB |
Output is correct |
11 |
Correct |
112 ms |
66156 KB |
Output is correct |
12 |
Correct |
152 ms |
62956 KB |
Output is correct |
13 |
Correct |
206 ms |
66156 KB |
Output is correct |
14 |
Correct |
297 ms |
66924 KB |
Output is correct |
15 |
Correct |
187 ms |
65260 KB |
Output is correct |
16 |
Correct |
184 ms |
65388 KB |
Output is correct |
17 |
Correct |
146 ms |
66156 KB |
Output is correct |
18 |
Correct |
143 ms |
66156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1060 ms |
358636 KB |
Output is correct |
2 |
Correct |
1070 ms |
358660 KB |
Output is correct |
3 |
Correct |
1303 ms |
366444 KB |
Output is correct |
4 |
Correct |
946 ms |
359652 KB |
Output is correct |
5 |
Correct |
729 ms |
358636 KB |
Output is correct |
6 |
Correct |
748 ms |
358556 KB |
Output is correct |
7 |
Correct |
731 ms |
358676 KB |
Output is correct |
8 |
Correct |
729 ms |
358508 KB |
Output is correct |
9 |
Correct |
523 ms |
344684 KB |
Output is correct |
10 |
Correct |
562 ms |
359432 KB |
Output is correct |
11 |
Correct |
585 ms |
363116 KB |
Output is correct |
12 |
Correct |
712 ms |
363828 KB |
Output is correct |
13 |
Correct |
961 ms |
365772 KB |
Output is correct |
14 |
Correct |
1327 ms |
369572 KB |
Output is correct |
15 |
Correct |
909 ms |
366300 KB |
Output is correct |
16 |
Incorrect |
909 ms |
366328 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |