| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 959275 |
2024-04-07T19:28:51 Z |
qin |
Bulldozer (JOI17_bulldozer) |
C++17 |
|
2000 ms |
348 KB |
//~ #pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef __int128 ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double db;
#define int ll
#define vv vector
/*void read(int &a){
char c = getchar_unlocked(); a = 0;
while(c<'0' || '9'<c) c = getchar_unlocked();
while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
struct pt{
int x, y, val;
pt(){ x = 0, y = 0, val = 0; }
pt(int X, int Y, int V){ x = X, y = Y, val = V; }
bool operator <(const pt &a) const{ return x != a.x ? x < a.x : y < a.y; }
};
const ll INF = 1e18;
ll gcd_(ll a, ll b){
if(a > b) swap(a, b);
while(a) b %= a, swap(a, b);
return b;
}
struct fr{
ll a, b;
fr(){ a = 0, b = 1; }
fr(ll A, ll B){
if(B < 0) A = -A, B = -B;
a = A/gcd_(A, B), b = B/gcd_(A, B);
}
bool operator <(const fr &x) const{
if(a == INF || x.a == INF) return a < x.a;
return a*x.b < x.a*b;
}
bool operator ==(const fr &x) const{
if(a == INF || x.a == INF) return a == x.a;
return a*x.b == x.a*b;
}
bool operator !=(const fr &x) const{
if(a == INF || x.a == INF) return a != x.a;
return a*x.b != x.a*b;
}
};
db eps = 1e-15;
bool equal(db a, db b){ return abs(b-a) < eps; }
struct line{
fr a, b;
int x1, x2, i, j;
line(){ a = fr(), b = fr(), x1 = 0, x2 = 0, i = 0, j = 0; }
line(int X1, int Y1, int X2, int Y2, int I, int J){
if(X1 == X2) a = fr(INF, 1), b = fr(), x1 = min(Y1, Y2), x2 = max(Y1, Y2);
else a = fr(Y2-Y1, X2-X1), b = fr((Y1*(X2-X1)-(Y2-Y1))*X1,X2-X1), x1 = min(X1, X2), x2 = max(X1, X2);
i = I, j = J;
}
bool operator <(const line &t) const{
if(a != t.a) return a < t.a;
else if(b != t.b) return b < t.b;
else if(x1 != t.x1) return x1 < t.x1;
return x2 < t.x2;
}
};
int base = 1;
struct seg{
struct Node{
int mx, mn, mx_delta;
Node(){ mx = -infll, mn = infll, mx_delta = -infll; }
Node(int val){ mx = val, mn = val, mx_delta = 0; }
};
vv<Node> t;
void init(int n, vv<int> &pf){
while(base < n) base <<= 1;
t.resize(base<<1);
for(int i = 1; i <= n; ++i) t[i+base-1] = Node(pf[i]);
for(int i = base-1; i; --i){
t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn);
t[i].mx_delta = max(t[i<<1|1].mx-t[i<<1].mn, max(t[i<<1].mx_delta, t[i<<1|1].mx_delta));
}
}
void update(int i, ll val){ //tutaj ewentualnie mozna dozylowywac
for(i += base-1, t[i] = Node(val), i >>= 1; i; i >>= 1){
t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn);
t[i].mx_delta = max(t[i<<1|1].mx-t[i<<1].mn, max(t[i<<1].mx_delta, t[i<<1|1].mx_delta));
}
}
int query(){ return max(t[1].mx, t[1].mx_delta); }
};
void answer(){
int n; scanf("%lld", &n);
vv<pt> p(n+1);
for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
sort(1+all(p));
vv<line> t((n*(n-1))/2);
for(int i = 1, l = 0; i <= n-1; ++i)
for(int j = i+1; j <= n; ++j, ++l) t[l] = line(p[i].x, p[i].y, p[j].x, p[j].y, i, j);
sort(all(t));
//~ for(line &u : t) cout << setprecision(20) << fixed << u.a << " " << u.b <<"\n";//printf("%f %f %d %d\n", u.a, u.b, u.x1, u.x2);
vv<ll> pf(n+1);
vv<int> pos(n+1);
for(int i = 1; i <= n; ++i) pf[i] = pf[i-1]+p[i].val, pos[i] = i;
seg seg; seg.init(n, pf);
int result = max(int(0ll), seg.query());
//~ printf("%lld\n", result);
//~ for(int i = 1; i <= n; ++i) printf("%lld ", pf[i]);
//~ pn;
for(int i = 0; i < ssize(t); ++i){
int a = t[i].i, b = t[i].j; //assert(abs(pos[a]-pos[b]) == 1);
if(pos[b] < pos[a]) swap(a, b);
pf[pos[a]] += p[b].val-p[a].val;
swap(pos[a], pos[b]);
seg.update(pos[a], pf[pos[a]]), seg.update(pos[b], pf[pos[b]]);
while(i+1 < ssize(t) && t[i+1].a == t[i].a){
++i;
a = t[i].i, b = t[i].j; //assert(abs(pos[a]-pos[b]) == 1);
if(pos[b] < pos[a]) swap(a, b);
pf[pos[a]] += p[b].val-p[a].val;
swap(pos[a], pos[b]);
seg.update(pos[a], pf[pos[a]]), seg.update(pos[b], pf[pos[b]]);
}
result = max(result, seg.query());
//~ printf("%lld\n", seg.query());
//~ for(int j = 1; j <= n; ++j) printf("%lld ", pf[j]);
//~ pn;
}
printf("%lld\n", result);
}
signed main(){
int T = 1;
//~ scanf("%d", &T);
//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
for(++T; --T; ) answer();
return 0;
}
Compilation message
bulldozer.cpp: In function 'void answer()':
bulldozer.cpp:105:20: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka '__int128*'} [-Wformat=]
105 | int n; scanf("%lld", &n);
| ~~~^ ~~
| | |
| | ll* {aka __int128*}
| long long int*
bulldozer.cpp:107:41: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka '__int128*'} [-Wformat=]
107 | for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
| ~~~^ ~~~~~~~
| | |
| | ll* {aka __int128*}
| long long int*
bulldozer.cpp:107:45: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'll*' {aka '__int128*'} [-Wformat=]
107 | for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
| ~~~^ ~~~~~~~
| | |
| long long int* ll* {aka __int128*}
bulldozer.cpp:107:49: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'll*' {aka '__int128*'} [-Wformat=]
107 | for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
| ~~~^ ~~~~~~~~~
| | |
| long long int* ll* {aka __int128*}
bulldozer.cpp:145:14: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'll' {aka '__int128'} [-Wformat=]
145 | printf("%lld\n", result);
| ~~~^ ~~~~~~
| | |
| | ll {aka __int128}
| long long int
bulldozer.cpp:105:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | int n; scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
bulldozer.cpp:107:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
