_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long 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; }
};
db eps = 1e-19;
bool equal(db a, db b){ return abs(b-a) < eps; }
struct line{
db a, b;
int x1, x2, i, j;
line(){ a = 0, b = 0, 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 = 1e10, b = 0, x1 = min(Y1, Y2), x2 = max(Y1, Y2);
else a = (Y2-Y1)/db(X2-X1), b = db(Y1)-a*X1, x1 = min(X1, X2), x2 = max(X1, X2);
i = I, j = J;
}
bool operator <(const line &t) const{
if(!equal(a, t.a)) return a < t.a;
else if(!equal(b, t.b)) return b < t.b;
else if(!equal(x1, t.x1)) return x1 < t.x1;
return x2 < t.x2;
}
};
int base = 1;
struct seg{
struct Node{
ll mx, mn, mx_delta;
Node(){ mx = -infll, mn = infll, mx_delta = -infll; }
Node(ll val){ mx = val, mn = val, mx_delta = 0; }
};
vv<Node> t;
void init(int n, vv<ll> &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));
}
}
ll 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);
ll result = max(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) && equal(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:1:10: error: expected constructor, destructor, or type conversion before '(' token
1 | _popcount(x)
| ^
bulldozer.cpp:6:9: error: 'pair' does not name a type
6 | typedef pair<int, int> pii;
| ^~~~
bulldozer.cpp:7:9: error: 'pair' does not name a type
7 | typedef pair<int, ll> pil;
| ^~~~
bulldozer.cpp:8:9: error: 'pair' does not name a type
8 | typedef pair<ll, int> pli;
| ^~~~
bulldozer.cpp:9:9: error: 'pair' does not name a type
9 | typedef pair<ll, ll> pll;
| ^~~~
bulldozer.cpp: In function 'bool equal(db, db)':
bulldozer.cpp:26:32: error: 'abs' was not declared in this scope
26 | bool equal(db a, db b){ return abs(b-a) < eps; }
| ^~~
bulldozer.cpp: In constructor 'line::line(ll, ll, ll, ll, ll, ll)':
bulldozer.cpp:32:40: error: 'min' was not declared in this scope
32 | if(X1 == X2) a = 1e10, b = 0, x1 = min(Y1, Y2), x2 = max(Y1, Y2);
| ^~~
bulldozer.cpp:32:58: error: 'max' was not declared in this scope
32 | if(X1 == X2) a = 1e10, b = 0, x1 = min(Y1, Y2), x2 = max(Y1, Y2);
| ^~~
bulldozer.cpp:33:55: error: 'min' was not declared in this scope
33 | else a = (Y2-Y1)/db(X2-X1), b = db(Y1)-a*X1, x1 = min(X1, X2), x2 = max(X1, X2);
| ^~~
bulldozer.cpp:33:73: error: 'max' was not declared in this scope
33 | else a = (Y2-Y1)/db(X2-X1), b = db(Y1)-a*X1, x1 = min(X1, X2), x2 = max(X1, X2);
| ^~~
bulldozer.cpp: At global scope:
bulldozer.cpp:12:12: error: 'vector' does not name a type
12 | #define vv vector
| ^~~~~~
bulldozer.cpp:50:3: note: in expansion of macro 'vv'
50 | vv<Node> t;
| ^~
bulldozer.cpp:12:12: error: 'vector' has not been declared
12 | #define vv vector
| ^~~~~~
bulldozer.cpp:51:20: note: in expansion of macro 'vv'
51 | void init(int n, vv<ll> &pf){
| ^~
bulldozer.cpp:51:22: error: expected ',' or '...' before '<' token
51 | void init(int n, vv<ll> &pf){
| ^
bulldozer.cpp: In member function 'void seg::init(ll, int)':
bulldozer.cpp:53:5: error: 't' was not declared in this scope; did you mean 'pt'?
53 | t.resize(base<<1);
| ^
| pt
bulldozer.cpp:54:52: error: 'pf' was not declared in this scope; did you mean 'pt'?
54 | for(int i = 1; i <= n; ++i) t[i+base-1] = Node(pf[i]);
| ^~
| pt
bulldozer.cpp:56:17: error: 'max' was not declared in this scope
56 | t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
| ^~~
bulldozer.cpp:57:17: error: 'min' was not declared in this scope
57 | t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn);
| ^~~
bulldozer.cpp: In member function 'void seg::update(ll, ll)':
bulldozer.cpp:62:22: error: 't' was not declared in this scope; did you mean 'pt'?
62 | for(i += base-1, t[i] = Node(val), i >>= 1; i; i >>= 1){
| ^
| pt
bulldozer.cpp:63:17: error: 'max' was not declared in this scope
63 | t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
| ^~~
bulldozer.cpp:64:17: error: 'min' was not declared in this scope
64 | t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn);
| ^~~
bulldozer.cpp: In member function 'll seg::query()':
bulldozer.cpp:68:26: error: 't' was not declared in this scope; did you mean 'pt'?
68 | ll query(){ return max(t[1].mx, t[1].mx_delta); }
| ^
| pt
bulldozer.cpp:68:22: error: 'max' was not declared in this scope
68 | ll query(){ return max(t[1].mx, t[1].mx_delta); }
| ^~~
bulldozer.cpp: In function 'void answer()':
bulldozer.cpp:71:10: error: 'scanf' was not declared in this scope
71 | int n; scanf("%lld", &n);
| ^~~~~
bulldozer.cpp:12:12: error: 'vector' was not declared in this scope
12 | #define vv vector
| ^~~~~~
bulldozer.cpp:72:3: note: in expansion of macro 'vv'
72 | vv<pt> p(n+1);
| ^~
bulldozer.cpp:72:8: error: expected primary-expression before '>' token
72 | vv<pt> p(n+1);
| ^
bulldozer.cpp:72:10: error: 'p' was not declared in this scope
72 | vv<pt> p(n+1);
| ^
bulldozer.cpp:74:10: error: 'all' was not declared in this scope; did you mean 'll'?
74 | sort(1+all(p));
| ^~~
| ll
bulldozer.cpp:74:3: error: 'sort' was not declared in this scope; did you mean 'short'?
74 | sort(1+all(p));
| ^~~~
| short
bulldozer.cpp:75:10: error: expected primary-expression before '>' token
75 | vv<line> t((n*(n-1))/2);
| ^
bulldozer.cpp:75:12: error: 't' was not declared in this scope
75 | vv<line> t((n*(n-1))/2);
| ^
bulldozer.cpp:81:8: error: expected primary-expression before '>' token
81 | vv<ll> pf(n+1);
| ^
bulldozer.cpp:81:10: error: 'pf' was not declared in this scope; did you mean 'pt'?
81 | vv<ll> pf(n+1);
| ^~
| pt
bulldozer.cpp:82:9: error: expected primary-expression before '>' token
82 | vv<int> pos(n+1);
| ^
bulldozer.cpp:82:11: error: 'pos' was not declared in this scope
82 | vv<int> pos(n+1);
| ^~~
bulldozer.cpp:87:15: error: 'max' was not declared in this scope
87 | ll result = max(0ll, seg.query());
| ^~~
bulldozer.cpp:91:22: error: 'ssize' was not declared in this scope
91 | for(int i = 0; i < ssize(t); ++i){
| ^~~~~
bulldozer.cpp:93:12: error: 'b' was not declared in this scope
93 | if(pos[b] < pos[a]) swap(a, b);
| ^
bulldozer.cpp:93:25: error: 'swap' was not declared in this scope
93 | if(pos[b] < pos[a]) swap(a, b);
| ^~~~
bulldozer.cpp:94:21: error: 'b' was not declared in this scope
94 | pf[pos[a]] += p[b].val-p[a].val;
| ^
bulldozer.cpp:95:5: error: 'swap' was not declared in this scope
95 | swap(pos[a], pos[b]);
| ^~~~
bulldozer.cpp:111:3: error: 'printf' was not declared in this scope
111 | printf("%lld\n", result);
| ^~~~~~
bulldozer.cpp:1:1: note: 'printf' is defined in header '<cstdio>'; did you forget to '#include <cstdio>'?
+++ |+#include <cstdio>
1 | _popcount(x)
