# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
937919 |
2024-03-04T16:44:39 Z |
danikoynov |
Teams (IOI15_teams) |
C++14 |
|
4000 ms |
14472 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segment
{
int l, r;
segment(int _l = 0, int _r = 0)
{
l = _l;
r = _r;
}
};
const int maxn = 5e5 + 10;
int n;
segment s[maxn];
void init(int N, int A[], int B[])
{
n = N;
for (int i = 1; i <= n; i ++)
{
s[i] = segment(A[i - 1], B[i - 1]);
}
}
int zeta(int a, int b)
{
int cnt = 0;
for (int i = 1; i <= n; i ++)
{
if (s[i].l <= a && s[i].r >= a)
continue;
if (s[i].l <= b && s[i].r >= b)
cnt ++;
}
return cnt;
}
int pivot_change(int a, int b, int diff)
{
/// dp_a + z(a, i) > dp_b + z(b, i)
/// dp_b - dp_a < z(a, i) - z(b, i)
/// diff < ....
int lf = b, rf = n;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (diff < zeta(a, mf) - zeta(b, mf))
lf = mf + 1;
else
rf = mf - 1;
}
return lf;
}
int dp[maxn];
int can(int M, int K[])
{
sort(K, K + M);
set < int > act;
set < pair < int, int > > event;
for (int i = 0; i < M; i ++)
{
while(!event.empty() && (*event.begin()).first <= K[i])
{
set < int > :: iterator it = act.find((*event.begin()).second);
event.erase({pivot_change(K[*prev(it)], K[*it], dp[*it] - dp[*prev(it)]), *it});
if (next(it) != act.end())
{
event.erase({pivot_change(K[*it], K[*next(it)], dp[*next(it)] - dp[*it]), *next(it)});
event.insert({pivot_change(K[*prev(it)], K[*next(it)], dp[*next(it)] - dp[*prev(it)]), *next(it)});
}
act.erase(it);
}
dp[i] = zeta(0, K[i]) - K[i];
if (!act.empty())
{
int bk = *act.rbegin();
dp[i] = min(dp[i], dp[bk] + zeta(K[bk], K[i]) - K[i]);
}
/**for (int j : act)
{
dp[i] = min(dp[i], dp[j] + zeta(K[j], K[i]) - K[i]);
}*/
if (dp[i] < 0)
return 0;
if (!act.empty())
{
int bk = *act.rbegin();
event.insert({pivot_change(K[bk], K[i], dp[i] - dp[bk]), i});
}
act.insert(i);
}
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5976 KB |
Output is correct |
2 |
Correct |
4 ms |
5980 KB |
Output is correct |
3 |
Correct |
2 ms |
5980 KB |
Output is correct |
4 |
Correct |
2 ms |
5980 KB |
Output is correct |
5 |
Correct |
1 ms |
5980 KB |
Output is correct |
6 |
Correct |
2 ms |
5980 KB |
Output is correct |
7 |
Correct |
7 ms |
5980 KB |
Output is correct |
8 |
Correct |
5 ms |
5976 KB |
Output is correct |
9 |
Correct |
2 ms |
5980 KB |
Output is correct |
10 |
Correct |
4 ms |
5980 KB |
Output is correct |
11 |
Correct |
2 ms |
5980 KB |
Output is correct |
12 |
Correct |
8 ms |
5980 KB |
Output is correct |
13 |
Correct |
5 ms |
5980 KB |
Output is correct |
14 |
Correct |
5 ms |
5980 KB |
Output is correct |
15 |
Correct |
2 ms |
5980 KB |
Output is correct |
16 |
Correct |
2 ms |
5980 KB |
Output is correct |
17 |
Correct |
2 ms |
5980 KB |
Output is correct |
18 |
Correct |
2 ms |
5980 KB |
Output is correct |
19 |
Correct |
3 ms |
5980 KB |
Output is correct |
20 |
Correct |
2 ms |
5980 KB |
Output is correct |
21 |
Correct |
2 ms |
6140 KB |
Output is correct |
22 |
Correct |
2 ms |
5980 KB |
Output is correct |
23 |
Correct |
2 ms |
5976 KB |
Output is correct |
24 |
Correct |
2 ms |
5980 KB |
Output is correct |
25 |
Correct |
2 ms |
5980 KB |
Output is correct |
26 |
Correct |
2 ms |
5980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
6748 KB |
Output is correct |
2 |
Correct |
6 ms |
6744 KB |
Output is correct |
3 |
Correct |
6 ms |
6744 KB |
Output is correct |
4 |
Correct |
8 ms |
7260 KB |
Output is correct |
5 |
Execution timed out |
4064 ms |
6748 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2107 ms |
7292 KB |
Output is correct |
2 |
Correct |
2627 ms |
7284 KB |
Output is correct |
3 |
Execution timed out |
4021 ms |
8372 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4008 ms |
14472 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |