Submission #93389

#	Time	Username	Problem	Language	Result	Execution time	Memory
93389		jasony123123	Svjetlost (COI18_svjetlost)	C++11	100 / 100	1216 ms	70708 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/***************************COI 2018 P3-Svjetlost******************************/
#define X first
#define Y second

ll ccw(pii a, pii b, pii c) {
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

bool cmp(pii a, pii b) {
	bool flg1 = a < mp(0, 0);
	bool flg2 = b < mp(0, 0);
	if (flg1 != flg2) return flg1 < flg2;
	return ccw(mp(0, 0), a, b) > 0;
}

struct upd {
	pii s, e;
	double d;
	upd(pii a, pii b, double c) : s(a), e(b), d(c) {}
};

int N;
pii A[100000 + 9];
v<upd> allu[100000 + 9];
int Q;
set<int> active;

upd getu(int cur, int nex, int flag) {
	pii start = mp(A[cur].X - A[nex].X, A[cur].Y - A[nex].Y);
	pii endi = mp(-start.X, -start.Y);
	double dist = flag*hypot(start.X, start.Y);
	return upd(start, endi, dist);
}
int getn(int cur) {
	auto it = active.upper_bound(cur);
	if (it != active.end()) return *it;
	else return *active.begin();
}
int getp(int cur) {
	auto it = active.find(cur);
	assert(it != active.end());
	if (it == active.begin()) return *active.rbegin();
	else return *(--it);
}

void setup() { // setup allu
	cin >> N;
	FOR(i, 0, N) cin >> A[i].X >> A[i].Y;
	A[N] = A[0];

	FOR(i, 0, N) {
		allu[0].push_back(getu(i, i + 1, 1));
	//	pf("allu[%d] push { %d -> %d  * %d } \n", 0, i, i + 1, 1);
	}

	FOR(i, 0, N) active.insert(i);
	cin >> Q;
	FORE(i, 1, Q) { // allu
		int cur;
		cin >> cur;
		cur--;
		int nex = getn(cur), pre = getp(cur);
		allu[i].push_back(getu(cur, nex, -1));
		allu[i].push_back(getu(pre, cur, -1));
		allu[i].push_back(getu(pre, nex, +1));
	//	pf("allu[%d] push { %d -> %d  * %d } \n", i, cur, nex, -1);
	//	pf("allu[%d] push { %d -> %d  * %d } \n", i, pre, cur, -1);
	//	pf("allu[%d] push { %d -> %d  * %d } \n", i, pre, nex, +1);
		active.erase(cur);
	}
}

template <class T> struct LazySegmentTree {
	int SZ;
	v<T> data, lazy;
	T id = 0;

	void init(int n) {
		data = v<T>(4 * n, id), lazy = v<T>(4 * n, id);
		SZ = n;
	}
	void prop(int ind, int L, int R) {
		if (lazy[ind] != id) {
			data[ind] += lazy[ind];
			if (L != R) {
				lazy[2 * ind] += lazy[ind];
				lazy[2 * ind + 1] += lazy[ind];
			}
			lazy[ind] = id;
		}
	}
	void combine(int ind) {
		data[ind] = max(data[2 * ind], data[2 * ind + 1]);
	}

	T query(int lo, int hi) { // [lo,hi]
		return query(lo, hi, 1, 0, SZ - 1);
	}
	T query(int lo, int hi, int ind, int L, int R) {
		prop(ind, L, R);
		if (lo > R || L > hi) return id;
		if (lo <= L && R <= hi) return data[ind];
		int M = (L + R) / 2;
		return max(query(lo, hi, 2 * ind, L, M), query(lo, hi, 2 * ind + 1, M + 1, R));
	}

	void update(int lo, int hi, T val) {
		update(lo, hi, val, 1, 0, SZ - 1);
	}
	void update(int lo, int hi, T val, int ind, int L, int R) {
		prop(ind, L, R);
		if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) {
			lazy[ind] += val;
			prop(ind, L, R);
			return;
		}
		int M = (L + R) / 2;
		update(lo, hi, val, 2 * ind, L, M); update(lo, hi, val, 2 * ind + 1, M + 1, R);
		combine(ind);
	}
};


//template <class T> struct LazySegmentTree {
//	int SZ;
//	v<T> data;
//	T id = 0;
//
//	void init(int n) {
//		data = v<T>(4 * n, id);
//		SZ = n;
//	}
//	T query(int lo, int hi) { // [lo,hi]
//		T ret = id;
//		FORE(i, lo, hi) maxx(ret, data[i]);
//		return ret;
//	}
//
//	void update(int lo, int hi, T val) {
//		FORE(i, lo, hi) data[i] += val;
//	}
//};

LazySegmentTree<double> tree;

int main() {
	io();
	setup();
	v<pii> dat = { {0, -1} };
	FORE(i, 0, Q) for (auto u : allu[i]) {
		dat.push_back(u.s);
		dat.push_back(u.e);
		dat.push_back({ -u.s.Y, u.s.X });
	}
	//cout << "Raw\n";
	//for (auto p : dat) {
	//	cout << p.X << " " << p.Y << "\n";
	//}
	sort(dat.begin(), dat.end(), cmp);
	//cout << "Sorted\n";
	//for (auto p : dat) {
	//	cout << p.X << " " << p.Y << "\n";
	//}
	dat.resize(unique(dat.begin(), dat.end(), [&](const pii &a, const pii &b) { return !cmp(a, b) && !cmp(b, a); }) - dat.begin());
	//cout << "Uniq\n";
	//for (auto p : dat) {
	//	cout << p.X << " " << p.Y << "\n";
	//}

	cout << fixed << setprecision(10);
	int M = dat.size();
	tree.init(M);
	FORE(i, 0, Q) {
		for (auto u : allu[i]) {
			int lo = lower_bound(all(dat), u.s, cmp) - dat.begin();
			int hi = lower_bound(all(dat), u.e, cmp) - dat.begin();
			hi--;
			if (hi < 0) hi = M - 1;
			if (lo > hi)
				tree.update(lo, M-1, u.d), tree.update(0, hi, u.d);
			else
				tree.update(lo, hi, u.d);
		//	cout << lo << " - " << hi << ": " << u.d << "\n";
		}
		cout << tree.query(0, M - 1) << "\n";
	//	cout << "Query\n";
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31