Submission #392839

#	Time	Username	Problem	Language	Result	Execution time	Memory
392839		asbsfds	Svjetlost (COI18_svjetlost)	C++14	100 / 100	1301 ms	50940 KiB

Main

#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 (stderr)

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 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31