oj.uz

Submission #392839

# Submission time Handle Problem Language Result Execution time Memory
392839 2021-04-21T21:40:37 Z asbsfds Svjetlost (COI18_svjetlost) C++14
100 / 100
 1301 ms 50940 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 5e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

struct toc {
	int x, y;
	double ang;
	double len;
	
	toc (int x, int y, double ang) {
		this->x = x;
		this->y = y;
		this->ang = ang;
		len = -1;
	}
	
	toc() {
		x = y = ang = 0;
		len = -1;
	}
	
	pair<int, int> cords() {
		return make_pair(this->x, this->y);
	}
	
	double leng() {
		if (len != -1) return len;
		return len = sqrt((llint)x * x + (llint)y * y);
	}
};

int n, q;
pair<int, int> niz[maxn];
vector< toc > vec;
int qs[maxn];
set< int > s;
map< pair<int, int>, int > m;
double tour[treesiz];
double prop[treesiz];
int cal[maxn];
vector< pair<double, toc> > evs[maxn];

llint ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	return (llint)a.X * (b.Y - c.Y) + (llint)b.X * (c.Y - a.Y) + (llint)c.X * (a.Y - b.Y);
}

void send(int node) {
	prop[node * 2] += prop[node];
	prop[node * 2 + 1] += prop[node];
	
	tour[node * 2] += prop[node];
	tour[node * 2 + 1] += prop[node];
	prop[node] = 0;
}

void update(int a, int b, int l, int r, int node, double val) {
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		tour[node] += val;
		prop[node] += val;
		return;
	}
	
	int mid = (l + r) / 2;
	send(node);
	
	update(a, b, l, mid, node * 2, val);
	update(a, b, mid + 1, r, node * 2 + 1, val);
	tour[node] = max(tour[node * 2], tour[node * 2 + 1]);
}

double query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return 0.0;
	if (l >= a && r <= b) return tour[node];
	
	int mid = (l + r) / 2;
	send(node);
	return max(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

bool cmp(toc a, toc b) {
	return a.ang < b.ang;
}

toc mak(int x, int y) {
	//printf("making: %d %d\n", x, y);
	toc out;
	out.x = x;
	out.y = y;
	out.ang = atan2(y, x);
	return out;
}

inline toc conv(pair<int, int> a, pair<int, int> b) {
	return mak(b.X - a.X, b.Y - a.Y);
}

int check(int x, int y) {
	x %= vec.size();
	y %= vec.size();
	
	if (ccw(make_pair(0, 0), vec[x].cords(), vec[y].cords()) > 0) return true;
	return false;
}

void upd(int x, double val) {
	update(cal[x], x, 0, off - 1, 1, val);
	x += vec.size();
	update(cal[x], x, 0, off - 1, 1, val);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		niz[i] = make_pair(x, y);
	}
	
	for (int i = 0; i < n; i++) {
		vec.push_back(conv(niz[i], niz[(i + 1) % n]));
	}
	
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		scanf("%d", qs+i); qs[i]--;
	}
	
	for (int i = 0; i < n; i++) s.insert(i);
	
	for (int i = 0; i < q; i++) {
		int x = qs[i];
		
		auto iter = s.find(x);
		assert(iter != s.end());
		
		auto lef = iter;
		if (lef == s.begin()) {
			lef = s.end();
			lef--;
		} else lef--;
		
		auto rig = iter; rig++;
		if (rig == s.end()) rig = s.begin();
		
		vec.push_back(conv(niz[*lef], niz[*rig]));
		evs[i].push_back(make_pair(-1, conv(niz[*lef], niz[*iter])));
		evs[i].push_back(make_pair(-1, conv(niz[*iter], niz[*rig])));
		evs[i].push_back(make_pair(1, conv(niz[*lef], niz[*rig])));
		s.erase(iter);
	}
	
	sort(vec.begin(), vec.end(), cmp);
	
	//for (int i = 0; i < vec.size(); i++) {
	//	cout << vec[i].x << " " << vec[i].y << " " << vec[i].ang << "\n";
	//}
	
	int s = vec.size();
	for (int i = 0; i < s + s; i++) {
		int lo = max(0, i - s + 1);
		int hi = i;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (check(mid, i)) hi = mid;
			else lo = mid + 1;
		}
		cal[i] = lo;
		//printf("cal %d -> %d\n", i, cal[i]);
	}
	
	for (int i = 0; i < n; i++) {
		toc tren = conv(niz[i], niz[(i + 1) % n]);
		int ind = lower_bound(vec.begin(), vec.end(), tren, cmp) - vec.begin();
		//printf("debug: %d\n", ind);
		
		upd(ind, tren.leng());
	}
	
	cout << fixed << setprecision(6) << query(0, s - 1, 0, off - 1, 1) << '\n';
	
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < evs[i].size(); j++) {
			int mul = evs[i][j].first;
			toc tren = evs[i][j].second;
			
			int ind = lower_bound(vec.begin(), vec.end(), tren, cmp) - vec.begin();
			upd(ind, mul * tren.leng());
		}
		cout << fixed << setprecision(6) << query(0, s - 1, 0, off - 1, 1) << '\n';
	}
	return 0;
}

Compilation message

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:194:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, toc> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |   for (int j = 0; j < evs[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
svjetlost.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
svjetlost.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |   scanf("%d", qs+i); qs[i]--;
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12156 KB 11 numbers
2 Correct 10 ms 12196 KB 41 numbers
3 Correct 10 ms 12184 KB 11 numbers
4 Correct 9 ms 12188 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12156 KB 11 numbers
2 Correct 10 ms 12196 KB 41 numbers
3 Correct 10 ms 12184 KB 11 numbers
4 Correct 9 ms 12188 KB 93 numbers
5 Correct 12 ms 12364 KB 101 numbers
6 Correct 18 ms 12720 KB 1201 numbers
7 Correct 21 ms 12748 KB 1556 numbers
8 Correct 26 ms 12996 KB 1996 numbers
9 Correct 24 ms 12848 KB 1960 numbers
10 Correct 26 ms 12876 KB 1991 numbers
11 Correct 24 ms 12848 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12212 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 10 ms 12344 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 35 ms 13996 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 61 ms 15628 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 234 ms 26696 KB found '3142086769.6889710426', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 236 ms 26736 KB found '3142076120.8714637756', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12876 KB 1001 numbers
2 Correct 170 ms 19768 KB 15001 numbers
3 Correct 473 ms 30660 KB 44445 numbers
4 Correct 380 ms 31892 KB 22223 numbers
5 Correct 892 ms 47676 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12156 KB 11 numbers
2 Correct 10 ms 12196 KB 41 numbers
3 Correct 10 ms 12184 KB 11 numbers
4 Correct 9 ms 12188 KB 93 numbers
5 Correct 12 ms 12364 KB 101 numbers
6 Correct 18 ms 12720 KB 1201 numbers
7 Correct 21 ms 12748 KB 1556 numbers
8 Correct 26 ms 12996 KB 1996 numbers
9 Correct 24 ms 12848 KB 1960 numbers
10 Correct 26 ms 12876 KB 1991 numbers
11 Correct 24 ms 12848 KB 1963 numbers
12 Correct 8 ms 12212 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 10 ms 12344 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 35 ms 13996 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 61 ms 15628 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 234 ms 26696 KB found '3142086769.6889710426', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 236 ms 26736 KB found '3142076120.8714637756', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 20 ms 12876 KB 1001 numbers
19 Correct 170 ms 19768 KB 15001 numbers
20 Correct 473 ms 30660 KB 44445 numbers
21 Correct 380 ms 31892 KB 22223 numbers
22 Correct 892 ms 47676 KB 88889 numbers
23 Correct 1301 ms 50940 KB 98175 numbers
24 Correct 286 ms 22200 KB 25905 numbers
25 Correct 1018 ms 50212 KB 98169 numbers
26 Correct 1000 ms 47836 KB 91845 numbers
27 Correct 1024 ms 50240 KB 98296 numbers
28 Correct 915 ms 45760 KB 85384 numbers
29 Correct 879 ms 45472 KB 85317 numbers
30 Correct 1029 ms 50516 KB 98246 numbers
31 Correct 570 ms 37552 KB 50001 numbers