제출 #104377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104377		Noam527	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	3 ms	512 KiB

bulldozer

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct point {
	ll x, y, c, i;
	point() {}
	point(ll xx, ll yy, ll cc, int ii) {
		x = xx;
		y = yy;
		c = cc;
		i = ii;
	}
	bool operator < (const point &a) const {
		if (y != a.y) return y < a.y;
		return x < a.x;
	}
};

struct block {
	ll mx, L, R, S;
	block(ll v = -inf) {
		mx = L = R = S = v;
	}
	block operator * (const block &a) const {
		block rtn;
		rtn.S = S + a.S;
		rtn.L = max(L, S + a.L);
		rtn.R = max(R + a.S, a.R);
		rtn.mx = max(max(mx, a.mx), R + a.L);
		return rtn;
	}
};

struct segtree {
	int n;
	vector<block> t;
	segtree() {}
	segtree(const vector<point> &a) {
		n = max(2, (int)a.size());
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
		for (int i = 0; i < a.size(); i++)
			t[i + n - 1] = block(a[i].c);
		for (int i = n - 2; i >= 0; i--) fix(i);
	}
	void fix(int x) {
		t[x] = t[x + x + 1] * t[x + x + 2];
	}
	void upd(int x, ll v) {
		x += n - 1;
		t[x] = block(v);
		x = (x - 1) / 2;
		while (x) {
			fix(x);
			x = (x - 1) / 2;
		}
		fix(0);
	}
	ll query() {
		return t[0].mx;
	}
};

struct eve {
	ll x, y;
	int u, v;
	eve(ll xx = 0, ll yy = 0, int uu = 0, int vv = 0) {
		x = xx;
		y = yy;
		if (y < 0) {
			x = -x;
			y = -y;
		}
		u = uu;
		v = vv;
	}
	bool operator < (const eve &a) const {
		return x * a.y - y * a.x > 0;
	}
	bool operator == (const eve &a) const {
		return x * a.y == y * a.x;
	}
};

int n;
vector<point> a;
vector<int> ind;
vector<eve> E;
segtree T;

ll ans = 0;

void apply(int i, int j) {
	int u = a[i].i, v = a[j].i;
	if (OO) {
		cout << "swapping points\n";
		cout << a[i].x << " " << a[i].y << '\n';
		cout << a[j].x << " " << a[j].y << '\n';
		cout << "which is indicies " << i << " " << j << '\n';
		cout << "and in ind " << u << " " << v << '\n';
	}
	swap(a[i], a[j]);
	swap(ind[u], ind[v]);
	T.upd(i, a[i].c);
	T.upd(j, a[j].c);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	a.resize(n);
	E.reserve(n * (n - 1) / 2);
	for (auto &i : a) cin >> i.x >> i.y >> i.c;
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) a[i].i = i;
	ind.resize(n);
	for (int i = 0; i < n; i++) ind[i] = i;
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
		E.push_back(eve(a[j].x - a[i].x, a[j].y - a[i].y, i, j));
	sort(E.begin(), E.end());
	T = segtree(a);
	if (OO) {
		cout << "querying on\n";
		for (const auto &i : a) cout << i.x << " " << i.y << '\n';
		cout << "result = " << T.query() << '\n';
	}
	ans = max(ans, T.query());
	int nxt = 0;
	vector<pair<int, int>> those;
	while (nxt < E.size()) {
		those.clear();
		do {
			if (OO) cout << "adding event " << nxt << " " << E[nxt].x << " " << E[nxt].y << " " << E[nxt].u << " " << E[nxt].v << '\n';
			those.emplace_back(min(ind[E[nxt].u], ind[E[nxt].v]), max(ind[E[nxt].u], ind[E[nxt].v]));
			nxt++;
		} while (nxt < E.size() && E[nxt - 1] == E[nxt]);
		sort(those.begin(), those.end());
		for (const auto &i : those) apply(i.first, i.second);

		if (OO) {
			cout << "querying on\n";
			for (const auto &i : a) cout << i.x << " " << i.y << '\n';
			cout << "result = " << T.query() << '\n';
		}
		ans = max(ans, T.query());
		if (OO) {
			cout << "now ind = \n";
			for (const auto &i : ind) cout << i << " "; cout << '\n';
		}
	}
	finish(ans);
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In constructor 'segtree::segtree(const std::vector<point>&)':
bulldozer.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++)
                   ~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:138:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (nxt < E.size()) {
         ~~~~^~~~~~~~~~
bulldozer.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   } while (nxt < E.size() && E[nxt - 1] == E[nxt]);
            ~~~~^~~~~~~~~~
bulldozer.cpp:156:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (const auto &i : ind) cout << i << " "; cout << '\n';
    ^~~
bulldozer.cpp:156:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (const auto &i : ind) cout << i << " "; cout << '\n';
                                                ^~~~

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