| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 27031 | RayaBurong25_1 | Bulldozer (JOI17_bulldozer) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#define eps 0.000001
typedef struct point point;
struct point
{
double x, y;
int v, i;
};
std::vector<point> P;
typedef struct event event;
struct event
{
double ang;
int i1, i2; //ind and ind + 1 swap at ang
};
double abs(double a)
{
return (a < 0)?-a:a;
}
bool operator<(event a, event b)
{
return (a.ang > b.ang + eps);
}
std::priority_queue<event> E;
int sortxy(point a, point b)
{
return (a.x < b.x || (a.x == b.x && a.y > b.y));
}
double dist(point a, point b)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
int min(int a, int b)
{
return (a < b)?a:b;
}
int max(int a, int b)
{
return (a > b)?a:b;
}
typedef struct node node;
struct node
{
int summax, summin, ans;
};
node Seg[8005];
int Ind[2005];
void update(int pos, int val, int s, int e, int cell)
{
if (s == e)
{
Seg[cell].summax = val;
Seg[cell].summin = val;
Seg[cell].ans = 0;
// printf("upd s%d e%d %d %d %d\n", s, e, Seg[cell].summax, Seg[cell].summin, Seg[cell].ans);
return;
}
int m = (s + e)/2;
if (pos <= m)
update(pos, val, s, m, 2*cell + 1);
else
update(pos, val, m + 1, e, 2*cell + 2);
Seg[cell].summax = max(Seg[2*cell + 1].summax, Seg[2*cell + 2].summax);
Seg[cell].summin = min(Seg[2*cell + 1].summin, Seg[2*cell + 2].summin);
Seg[cell].ans = max(Seg[2*cell + 1].ans, Seg[2*cell + 2].ans);
Seg[cell].ans = max(Seg[cell].ans, Seg[2*cell + 2].summax - Seg[2*cell + 1].summin);
// printf("upd s%d e%d %d %d %d\n", s, e, Seg[cell].summax, Seg[cell].summin, Seg[cell].ans);
}
int query(int pos, int s, int e, int cell)
{
if (s == e)
return Seg[cell].summax;
int m = (s + e)/2;
if (pos <= m)
return query(pos, s, m, 2*cell + 1);
else
return query(pos, m + 1, e, 2*cell + 2);
}
int ans = 0;
int N;
void operate(int s, int e, double lim)
{
// printf("operate %d %d %lf\n", s, e, lim);
if (s >= e)
return;
std::reverse(P.begin() + s, P.begin() + e + 1);
int i;
int sum = 0;
if (s > 0)
sum = query(s, 0, N, 0);
for (i = s; i <= e; i++)
{
sum += P[i].v;
Ind[P[i].i] = i;
update(i + 1, sum, 0, N, 0);
}
ans = max(ans, Seg[0].ans);
double r;
if (s > 0)
{
r = acos((P[s].y - P[s - 1].y)/dist(P[s - 1], P[s]));
if (r > lim)
E.push({r, P[s - 1].i, P[s].i});
}
if (e + 1 < N)
{
r = acos((P[e + 1].y - P[e].y)/dist(P[e], P[e + 1]));
if (r > lim)
E.push({r, P[e].i, P[e + 1].i});
}
}
void printSeg(int s, int e, int cell)
{
if (s == e)
{
printf("%d: %d %d %d\n", s, Seg[cell].summin, Seg[cell].summax, Seg[cell].ans);
return;
}
int m = (s + e)/2;
printf("%d %d: %d %d %d\n", s, e, Seg[cell].summin, Seg[cell].summax, Seg[cell].ans);
printSeg(s, m, 2*cell + 1);
printSeg(m + 1, e, 2*cell + 2);
}
int main()
{
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
scanf("%d", &N);
// printf("N %d\n", N);
int i;
double x, y;
int v;
for (i = 0; i < N; i++)
{
scanf("%lf %lf %d", &x, &y, &v);
P.push_back({x, y, v, i});
}
std::sort(P.begin(), P.end(), sortxy);
for (i = 0; i < N - 1; i++)
E.push({acos((P[i + 1].y - P[i].y)/dist(P[i], P[i + 1])), P[i].i, P[i + 1].i});
// printf("N %d\n", N);
int sum = 0;
for (i = 0; i < N; i++)
{
sum += P[i].v;
Ind[P[i].i] = i;
// printf("sum %d\n", sum);
update(i + 1, sum, 0, N, 0);
// summin = min(summin, sum);
// ans = max(ans, sum - summin);
}
ans = max(ans, Seg[0].ans);
// printf("ans %d\n", ans);
event p;
int s, e;
while (!E.empty())
{
p = E.top();
E.pop();
s = Ind[p.i1];
e = Ind[p.i2];
if (e - s != 1)
continue;
// while (!E.empty() && abs(E.top().ang - p.ang) <= eps)
// {
// p = E.top();
// E.pop();
// if (p.ind == e)
// e = p.ind + 1;
// else
// {
// operate(s, e, p.ang);
// s = p.ind;
// e = p.ind + 1;
// }
// }
operate(s, e, p.ang);
// printSeg(0, N, 0);
// printf("ans %d\n", ans);
}
printf("%d", ans);
}