Submission #959275

#	Time	Username	Problem	Language	Result	Execution time	Memory
959275		qin	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	2047 ms	348 KiB

bulldozer

//~ #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 (stderr)

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);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20