oj.uz

Submission #93388

# Submission time Handle Problem Language Result Execution time Memory
93388 2019-01-08T03:12:03 Z jasony123123 Svjetlost (COI18_svjetlost) C++11
26 / 100
 3000 ms 23268 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;
	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 2808 KB 11 numbers
2 Correct 3 ms 2680 KB 41 numbers
3 Correct 3 ms 2684 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 2808 KB 11 numbers
2 Correct 3 ms 2680 KB 41 numbers
3 Correct 3 ms 2684 KB 11 numbers
4 Correct 4 ms 2808 KB 93 numbers
5 Correct 6 ms 2936 KB 101 numbers
6 Correct 29 ms 3448 KB 1201 numbers
7 Correct 44 ms 3632 KB 1556 numbers
8 Correct 67 ms 3856 KB 1996 numbers
9 Correct 65 ms 3720 KB 1960 numbers
10 Correct 67 ms 3840 KB 1991 numbers
11 Correct 65 ms 3848 KB 1963 numbers

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 7 ms 3064 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 131 ms 5464 KB found '31442617.6286691241', expected '31442617.6286691241', error '0.0000000000'
4 Correct 416 ms 7664 KB found '31424400.0534066744', expected '31424400.0534067489', error '0.0000000000'
5 Execution timed out 3039 ms 23268 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3700 KB 1001 numbers
2 Execution timed out 3056 ms 12752 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB 11 numbers
2 Correct 3 ms 2680 KB 41 numbers
3 Correct 3 ms 2684 KB 11 numbers
4 Correct 4 ms 2808 KB 93 numbers
5 Correct 6 ms 2936 KB 101 numbers
6 Correct 29 ms 3448 KB 1201 numbers
7 Correct 44 ms 3632 KB 1556 numbers
8 Correct 67 ms 3856 KB 1996 numbers
9 Correct 65 ms 3720 KB 1960 numbers
10 Correct 67 ms 3840 KB 1991 numbers
11 Correct 65 ms 3848 KB 1963 numbers
12 Correct 3 ms 2680 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 7 ms 3064 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 131 ms 5464 KB found '31442617.6286691241', expected '31442617.6286691241', error '0.0000000000'
15 Correct 416 ms 7664 KB found '31424400.0534066744', expected '31424400.0534067489', error '0.0000000000'
16 Execution timed out 3039 ms 23268 KB Time limit exceeded
17 Halted 0 ms 0 KB -