#include "teams.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
#define INF 1000000007
typedef struct point point;
struct point
{
int a, b;
};
typedef struct node node;
struct node
{
int sum;
node* l;
node* r;
};
int n;
node* root[500005];
int whichroot[500005];
int sortAB(point a, point b)
{
return (a.a < b.a || (a.a == b.a && a.b < b.b));
}
int max(int a, int b)
{
return (a > b)?a:b;
}
int min(int a, int b)
{
return (a < b)?a:b;
}
node* makeTree(int s, int e)
{
// printf("makeTree %d %d\n", s, e);
if (s == e)
{
node* p = new node();
p->sum = 0;
p->l = NULL;
p->r = NULL;
return p;
}
int m = (s + e)/2;
node* p = new node();
p->sum = 0;
p->l = makeTree(s, m);
p->r = makeTree(m + 1, e);
return p;
}
node* update(node* p, int s, int e, int v)
{
// printf("update p%p s%d e%d v%d\n", p, s, e, v);
if (s == e)
{
node* q = new node();
q->sum = p->sum + 1;
q->l = NULL;
q->r = NULL;
return q;
}
int m = (s + e)/2;
node* q = new node();
if (v <= m)
{
q->l = update(p->l, s, m, v);
q->r = p->r;
}
else
{
q->l = p->l;
q->r = update(p->r, m + 1, e, v);
}
q->sum = q->l->sum + q->r->sum;
return q;
}
void init(int N, int A[], int B[])
{
n = N;
std::vector<point> P;
int i;
for (i = 0; i < N; i++)
P.push_back({A[i], B[i]});
std::sort(P.begin(), P.end(), sortAB);
root[0] = makeTree(1, N);
for (i = 1; i <= N; i++)
{
root[i] = update(root[i - 1], 1, N, P[i - 1].b);
whichroot[P[i - 1].a] = i;
}
for (i = 1; i <= N; i++)
whichroot[i] = max(whichroot[i], whichroot[i - 1]);
// printf("init ok\n");
}
std::vector<std::pair<std::pair<int, int>, int> > Stairs;
int query(int Xmn, int Xmx, int Y)
{
// printf("query Xmn%d Xmx%d Y%d\n", Xmn, Xmx, Y);
if (Y < 1)
return 0;
node* p = root[whichroot[Xmx]];
node* q = root[whichroot[Xmn]];
int s = 1, e = n;
int m, r = 0;
while (s != e)
{
m = (s + e)/2;
if (Y <= m)
{
p = p->l;
q = q->l;
e = m;
}
else
{
r += p->l->sum - q->l->sum;
p = p->r;
q = q->r;
s = m + 1;
}
}
r += p->sum - q->sum;
return r;
}
int compStair(std::pair<std::pair<int, int>, int> e, int v)
{
return e.first.second > v;
}
int sumBoys(int Xmx, int Y)
{
// printf("sumBoys Xmx%d Y%d\n", Xmx, Y);
int i;
i = std::lower_bound(Stairs.begin(), Stairs.end(), Y, compStair) - Stairs.begin();
i--;
int Xmn = Stairs[i].first.first;
// printf("Xmn %d\n", Xmn);
int Q = query(Xmn, Xmx, Y) - (Stairs.back().second - Stairs[i].second);
// printf("Q %d\n", Q);
return Q;
}
void updStairs(int X, int Y, int K)
{
int sum = 0;
while (Stairs.back().first.second <= Y)
{
sum += Stairs.back().second;
Stairs.pop_back();
sum -= Stairs.back().second;
}
Stairs.push_back({{X, Y}, Stairs.back().second + sum + K});
// int i;
// for (i = 0; i < Stairs.size(); i++)
// printf("Stairs %d %d %d\n", Stairs[i].first.first, Stairs[i].first.second, Stairs[i].second);
}
int can(int M, int K[])
{
std::sort(&K[0], &K[M]);
Stairs.clear();
Stairs.push_back({{0, INF}, 0});
int i;
int mn, md, mx;
int sb, kisb;
for (i = 0; i < M; i++)
{
mn = K[i] - 1;
mx = n;
sb = sumBoys(K[i], mn);
if (sumBoys(K[i], mx) < K[i] + sb)
return 0;
kisb = K[i] + sb;
while (1)
{
// printf("mn %d mx %d\n", mn, mx);
if (mx - mn <= 1)
{
md = mx;
break;
}
md = (mn + mx)/2;
if (sumBoys(K[i], md) >= kisb)
mx = md;
else
mn = md;
}
updStairs(K[i], md, kisb);
}
return 1;
}
Compilation message
teams.cpp: In function 'int sumBoys(int, int)':
teams.cpp:133:67: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
i = std::lower_bound(Stairs.begin(), Stairs.end(), Y, compStair) - Stairs.begin();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
568 KB |
Output is correct |
6 |
Correct |
2 ms |
572 KB |
Output is correct |
7 |
Correct |
3 ms |
696 KB |
Output is correct |
8 |
Correct |
2 ms |
696 KB |
Output is correct |
9 |
Correct |
2 ms |
696 KB |
Output is correct |
10 |
Correct |
2 ms |
696 KB |
Output is correct |
11 |
Correct |
2 ms |
696 KB |
Output is correct |
12 |
Correct |
3 ms |
716 KB |
Output is correct |
13 |
Correct |
2 ms |
716 KB |
Output is correct |
14 |
Correct |
2 ms |
716 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
2 ms |
716 KB |
Output is correct |
17 |
Correct |
2 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
716 KB |
Output is correct |
19 |
Correct |
2 ms |
716 KB |
Output is correct |
20 |
Correct |
2 ms |
716 KB |
Output is correct |
21 |
Correct |
2 ms |
716 KB |
Output is correct |
22 |
Correct |
2 ms |
716 KB |
Output is correct |
23 |
Correct |
2 ms |
716 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
2 ms |
716 KB |
Output is correct |
26 |
Correct |
2 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
184 ms |
65128 KB |
Output is correct |
2 |
Correct |
239 ms |
65128 KB |
Output is correct |
3 |
Correct |
203 ms |
65164 KB |
Output is correct |
4 |
Correct |
207 ms |
65164 KB |
Output is correct |
5 |
Correct |
125 ms |
65164 KB |
Output is correct |
6 |
Correct |
125 ms |
65164 KB |
Output is correct |
7 |
Correct |
124 ms |
65164 KB |
Output is correct |
8 |
Correct |
127 ms |
65164 KB |
Output is correct |
9 |
Correct |
159 ms |
65164 KB |
Output is correct |
10 |
Correct |
131 ms |
65164 KB |
Output is correct |
11 |
Correct |
134 ms |
65956 KB |
Output is correct |
12 |
Correct |
136 ms |
65956 KB |
Output is correct |
13 |
Correct |
143 ms |
65956 KB |
Output is correct |
14 |
Correct |
131 ms |
65956 KB |
Output is correct |
15 |
Correct |
173 ms |
65956 KB |
Output is correct |
16 |
Correct |
193 ms |
65956 KB |
Output is correct |
17 |
Correct |
139 ms |
66100 KB |
Output is correct |
18 |
Correct |
139 ms |
66100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
200 ms |
66100 KB |
Output is correct |
2 |
Correct |
195 ms |
66100 KB |
Output is correct |
3 |
Correct |
750 ms |
67676 KB |
Output is correct |
4 |
Correct |
177 ms |
67676 KB |
Output is correct |
5 |
Correct |
286 ms |
67676 KB |
Output is correct |
6 |
Correct |
267 ms |
67676 KB |
Output is correct |
7 |
Correct |
141 ms |
67676 KB |
Output is correct |
8 |
Correct |
231 ms |
67676 KB |
Output is correct |
9 |
Correct |
152 ms |
67676 KB |
Output is correct |
10 |
Correct |
209 ms |
67676 KB |
Output is correct |
11 |
Correct |
227 ms |
67676 KB |
Output is correct |
12 |
Correct |
293 ms |
67676 KB |
Output is correct |
13 |
Correct |
535 ms |
67676 KB |
Output is correct |
14 |
Correct |
1004 ms |
67676 KB |
Output is correct |
15 |
Correct |
293 ms |
67676 KB |
Output is correct |
16 |
Correct |
303 ms |
67676 KB |
Output is correct |
17 |
Correct |
258 ms |
67676 KB |
Output is correct |
18 |
Correct |
261 ms |
67676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1194 ms |
358072 KB |
Output is correct |
2 |
Correct |
1177 ms |
358188 KB |
Output is correct |
3 |
Correct |
3550 ms |
360824 KB |
Output is correct |
4 |
Correct |
1470 ms |
360824 KB |
Output is correct |
5 |
Correct |
1451 ms |
360824 KB |
Output is correct |
6 |
Correct |
1139 ms |
360824 KB |
Output is correct |
7 |
Correct |
754 ms |
360824 KB |
Output is correct |
8 |
Correct |
995 ms |
362264 KB |
Output is correct |
9 |
Correct |
892 ms |
362264 KB |
Output is correct |
10 |
Correct |
922 ms |
370988 KB |
Output is correct |
11 |
Correct |
1123 ms |
374532 KB |
Output is correct |
12 |
Correct |
1330 ms |
378856 KB |
Output is correct |
13 |
Correct |
2853 ms |
384696 KB |
Output is correct |
14 |
Correct |
3986 ms |
390940 KB |
Output is correct |
15 |
Correct |
1446 ms |
399700 KB |
Output is correct |
16 |
Correct |
1443 ms |
406924 KB |
Output is correct |
17 |
Correct |
1071 ms |
413952 KB |
Output is correct |
18 |
Correct |
1048 ms |
420536 KB |
Output is correct |