oj.uz

Submission #93389

# Submission time Handle Problem Language Result Execution time Memory
93389 2019-01-08T03:13:11 Z jasony123123 Svjetlost (COI18_svjetlost) C++11
100 / 100
 1216 ms 70708 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB 11 numbers
2 Correct 4 ms 2680 KB 41 numbers
3 Correct 4 ms 2680 KB 11 numbers
4 Correct 4 ms 2808 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB 11 numbers
2 Correct 4 ms 2680 KB 41 numbers
3 Correct 4 ms 2680 KB 11 numbers
4 Correct 4 ms 2808 KB 93 numbers
5 Correct 5 ms 3064 KB 101 numbers
6 Correct 12 ms 3704 KB 1201 numbers
7 Correct 15 ms 3832 KB 1556 numbers
8 Correct 19 ms 4184 KB 1996 numbers
9 Correct 17 ms 4104 KB 1960 numbers
10 Correct 18 ms 4096 KB 1991 numbers
11 Correct 17 ms 4232 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 3192 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 21 ms 6380 KB found '31442617.6286691241', expected '31442617.6286691241', error '0.0000000000'
4 Correct 35 ms 9324 KB found '31424400.0534067228', expected '31424400.0534067489', error '0.0000000000'
5 Correct 149 ms 29408 KB found '3142086769.6889681816', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 150 ms 31332 KB found '3142076120.8714652061', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3956 KB 1001 numbers
2 Correct 119 ms 15712 KB 15001 numbers
3 Correct 346 ms 35204 KB 44445 numbers
4 Correct 309 ms 38896 KB 22223 numbers
5 Correct 716 ms 65336 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB 11 numbers
2 Correct 4 ms 2680 KB 41 numbers
3 Correct 4 ms 2680 KB 11 numbers
4 Correct 4 ms 2808 KB 93 numbers
5 Correct 5 ms 3064 KB 101 numbers
6 Correct 12 ms 3704 KB 1201 numbers
7 Correct 15 ms 3832 KB 1556 numbers
8 Correct 19 ms 4184 KB 1996 numbers
9 Correct 17 ms 4104 KB 1960 numbers
10 Correct 18 ms 4096 KB 1991 numbers
11 Correct 17 ms 4232 KB 1963 numbers
12 Correct 4 ms 2680 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 6 ms 3192 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 21 ms 6380 KB found '31442617.6286691241', expected '31442617.6286691241', error '0.0000000000'
15 Correct 35 ms 9324 KB found '31424400.0534067228', expected '31424400.0534067489', error '0.0000000000'
16 Correct 149 ms 29408 KB found '3142086769.6889681816', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 150 ms 31332 KB found '3142076120.8714652061', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 13 ms 3956 KB 1001 numbers
19 Correct 119 ms 15712 KB 15001 numbers
20 Correct 346 ms 35204 KB 44445 numbers
21 Correct 309 ms 38896 KB 22223 numbers
22 Correct 716 ms 65336 KB 88889 numbers
23 Correct 1216 ms 70708 KB 98175 numbers
24 Correct 237 ms 20452 KB 25905 numbers
25 Correct 904 ms 69944 KB 98169 numbers
26 Correct 777 ms 65592 KB 91845 numbers
27 Correct 884 ms 69956 KB 98296 numbers
28 Correct 803 ms 61896 KB 85384 numbers
29 Correct 738 ms 61356 KB 85317 numbers
30 Correct 889 ms 69824 KB 98246 numbers
31 Correct 459 ms 48440 KB 50001 numbers