Submission #1078762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078762		qwerasdfzxcl	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	664 ms	17344 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Node{
	ll prf, suf, sum, ans;
	Node(){}
	Node(ll x){
		if (x >= 0) prf = suf = sum = ans = x;
		else prf = suf = ans = 0, sum = x;
	}
	Node(ll _p, ll _s, ll _ss, ll _a): prf(_p), suf(_s), sum(_ss), ans(_a) {}

	Node operator + (const Node &N) const{
		return Node(max(prf, sum + N.prf), max(N.suf, suf + N.sum), sum + N.sum, max({ans, N.ans, suf + N.prf}));
	}
};

struct Seg{
	Node tree[4096];
	int sz, _n;

	void debug(){
		printf("A: ");
		for (int i=1;i<=_n;i++) printf("%lld ", tree[sz+i].sum);
		printf("\n");
		printf("ans = %lld\n", tree[1].ans);
		printf("\n");
	}

	void init(int n, array<int, 4> a[]){
		sz = 2048, _n = n;
		fill(tree, tree+sz*2, Node(0, 0, 0, 0));
		for (int i=1;i<=n;i++) tree[sz+i] = Node(a[i][2]);
		for (int i=sz-1;i;i--) tree[i] = tree[i<<1] + tree[i<<1|1];
	}

	void swap(int p, int q){
		p += sz, q += sz;
		std::swap(tree[p], tree[q]);
		for (p>>=1,q>>=1;p>0||q>0;p>>=1,q>>=1){
			tree[p] = tree[p<<1] + tree[p<<1|1];
			if (p!=q) tree[q] = tree[q<<1] + tree[q<<1|1];
		}
	}
}tree;

array<int, 4> a[2020];

int ccw(const array<int, 2> &P, const array<int, 2> &Q){
	ll ret = (ll)(a[P[1]][0] - a[P[0]][0]) * (a[Q[1]][1] - a[Q[0]][1]) - (ll)(a[P[1]][1] - a[P[0]][1]) * (a[Q[1]][0] - a[Q[0]][0]);
	if (ret > 0) return 1;
	if (ret < 0) return -1;
	return 0;
}

bool cmp(const array<int, 2> &P, const array<int, 2> &Q){
	int ret1 = ccw(P, Q);
	if (ret1) return ret1 > 0;
	return P < Q;
}

int main(){
	int n;
	scanf("%d", &n);

	for (int i=1;i<=n;i++){
		scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
	}

	sort(a+1, a+n+1);
	for (int i=1;i<=n;i++) a[i][3] = i; // ord

	vector<array<int, 2>> Ev;

	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			int ii = i, jj = j; // ii -> jj
			if ((a[i][0] < a[j][0]) || (a[i][0]==a[j][0] && a[i][1] < a[j][1])) swap(ii, jj);
			Ev.push_back({ii, jj});
		}
	}

	sort(Ev.begin(), Ev.end(), cmp);
	tree.init(n, a);
	ll ans = tree.tree[1].ans;

	for (int l=0,r;l<(int)Ev.size();l=r){
		for (r=l;r<(int)Ev.size() && !ccw(Ev[l], Ev[r]);r++);
		for (int i=l;i<r;i++){
			int &p = a[Ev[i][0]][3], &q = a[Ev[i][1]][3];
			assert(abs(p-q) == 1);
			
			tree.swap(p, q);
			swap(p, q);
		}

		ans = max(ans, tree.tree[1].ans);
	}

	printf("%lld\n", ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bulldozer.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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