oj.uz

Submission #44452

# Submission time Handle Problem Language Result Execution time Memory
44452 2018-04-02T07:52:44 Z Yehezkiel Svjetlost (COI18_svjetlost) C++11
100 / 100
 1181 ms 125008 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 100005;

int n;
pi a[MAXN];

double dist(pi a, pi b){
	return hypot(b.first - a.first, b.second - a.second);
}

lint ccw(pi a, pi b, pi 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;
}

pi sub(pi a, pi b){
	return pi(b.first - a.first, b.second - a.second);
}

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

struct query1{
	pi l, r;
	int time;
	double val;
};

struct query2{
	int s, e;
	double val;
};

vector<query1> v;
vector<query2> w[MAXN];

struct seg{
	vector<double> tree;
	vector<double> lazy;
	void init(int n){
		tree.resize(4 * n + 4);
		lazy.resize(4 * n + 4);
	}
	void lazydown(int p){
		tree[2*p] += lazy[p];
		tree[2*p+1] += lazy[p];
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, double v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] += v;
			lazy[p] += v;
			return;
		}
		lazydown(p);
		int pm = (ps+pe)/2;
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = max(tree[2*p], tree[2*p+1]);
	}
}seg;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d %d",&a[i].first,&a[i].second);
	a[n] = a[0];
	set<int> s;
	for(int i=0; i<n; i++) s.insert(i);
	for(int i=0; i<n; i++){
		v.push_back({sub(a[i+1], a[i]), sub(a[i], a[i+1]), 0, +dist(a[i], a[i+1])});
	}
	int q;
	scanf("%d",&q);
	for(int i=1; i<=q; i++){
		int x;
		scanf("%d",&x);
		x--;
		int nxt = x;
		s.erase(x);
		auto l = s.upper_bound(x);
		if(l == s.end()) l = s.begin();
		int nxtr = *l;
		l = s.lower_bound(x);
		if(l == s.begin()) l = s.end();
		l--;
		int nxtl = *l;
		v.push_back({sub(a[nxtr], a[nxt]), sub(a[nxt], a[nxtr]), i, -dist(a[nxt], a[nxtr])});
		v.push_back({sub(a[nxt], a[nxtl]), sub(a[nxtl], a[nxt]), i, -dist(a[nxt], a[nxtl])});
		v.push_back({sub(a[nxtr], a[nxtl]), sub(a[nxtl], a[nxtr]), i, +dist(a[nxtr], a[nxtl])});
	}
	vector<pi> crd;
	crd.push_back(pi(0, -1)); // last guy
	for(auto &i : v){
		crd.push_back(i.l);
		crd.push_back(i.r);
	}
	sort(crd.begin(), crd.end(), cmp);
	crd.resize(unique(crd.begin(), crd.end(), [&](const pi &a, const pi &b){
		return !cmp(a, b) && !cmp(b, a);
	}) - crd.begin());
	int M = 2 * crd.size();
	for(auto &i : v){
		int idx1 = lower_bound(crd.begin(), crd.end(), i.l, cmp) - crd.begin() + 1;
		int idx2 = lower_bound(crd.begin(), crd.end(), i.r, cmp) - crd.begin() + 1;
		if(idx1 < idx2){
			w[i.time].push_back({2 * idx1 + 1, 2 * idx2 - 1, i.val});
		}
		else{
			w[i.time].push_back({2 * idx1 + 1, M, i.val});
			w[i.time].push_back({1, 2 * idx2 - 1, i.val});
		}
	}
	vector<double> arr(M + 1);
	seg.init(M);
	for(int i=0; i<=q; i++){
		for(auto &j : w[i]){
			seg.add(j.s, j.e, 1, M, 1, j.val);
		}
		printf("%.10f\n", seg.tree[1]);
	}
}

Compilation message

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
svjetlost.cpp:78:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d %d",&a[i].first,&a[i].second);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
svjetlost.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB 11 numbers
2 Correct 4 ms 2788 KB 41 numbers
3 Correct 4 ms 2992 KB 11 numbers
4 Correct 4 ms 2992 KB 93 numbers
5 Correct 5 ms 3364 KB 101 numbers
6 Correct 12 ms 4004 KB 1201 numbers
7 Correct 16 ms 4392 KB 1556 numbers
8 Correct 24 ms 4992 KB 1996 numbers
9 Correct 21 ms 4992 KB 1960 numbers
10 Correct 18 ms 5024 KB 1991 numbers
11 Correct 22 ms 5120 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 ms 5120 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 22 ms 8544 KB found '31442617.6286691241', expected '31442617.6286691241', error '0.0000000000'
4 Correct 39 ms 13016 KB found '31424400.0534067266', expected '31424400.0534067489', error '0.0000000000'
5 Correct 185 ms 42548 KB found '3142086769.6889681816', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 188 ms 44372 KB found '3142076120.8714632988', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 44372 KB 1001 numbers
2 Correct 139 ms 44372 KB 15001 numbers
3 Correct 392 ms 53556 KB 44445 numbers
4 Correct 324 ms 56912 KB 22223 numbers
5 Correct 763 ms 99304 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB 11 numbers
2 Correct 4 ms 2788 KB 41 numbers
3 Correct 4 ms 2992 KB 11 numbers
4 Correct 4 ms 2992 KB 93 numbers
5 Correct 5 ms 3364 KB 101 numbers
6 Correct 12 ms 4004 KB 1201 numbers
7 Correct 16 ms 4392 KB 1556 numbers
8 Correct 24 ms 4992 KB 1996 numbers
9 Correct 21 ms 4992 KB 1960 numbers
10 Correct 18 ms 5024 KB 1991 numbers
11 Correct 22 ms 5120 KB 1963 numbers
12 Correct 5 ms 5120 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 5 ms 5120 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 22 ms 8544 KB found '31442617.6286691241', expected '31442617.6286691241', error '0.0000000000'
15 Correct 39 ms 13016 KB found '31424400.0534067266', expected '31424400.0534067489', error '0.0000000000'
16 Correct 185 ms 42548 KB found '3142086769.6889681816', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 188 ms 44372 KB found '3142076120.8714632988', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 13 ms 44372 KB 1001 numbers
19 Correct 139 ms 44372 KB 15001 numbers
20 Correct 392 ms 53556 KB 44445 numbers
21 Correct 324 ms 56912 KB 22223 numbers
22 Correct 763 ms 99304 KB 88889 numbers
23 Correct 1181 ms 108416 KB 98175 numbers
24 Correct 273 ms 108416 KB 25905 numbers
25 Correct 908 ms 111928 KB 98169 numbers
26 Correct 821 ms 111928 KB 91845 numbers
27 Correct 888 ms 117520 KB 98296 numbers
28 Correct 847 ms 117520 KB 85384 numbers
29 Correct 781 ms 117520 KB 85317 numbers
30 Correct 886 ms 125008 KB 98246 numbers
31 Correct 488 ms 125008 KB 50001 numbers