Submission #1016075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016075		vjudge1	Wish (LMIO19_noras)	C++17	100 / 100	99 ms	8660 KiB

noras

#include <bits/stdc++.h>
using namespace std;
#define big __int128_t
// #define big long long

const long double eps = 1e-12;
const long long inf = 1LL << 60;
const long long lim = 1e9;

long long R, sx, sy, sx2, sy2, vx, vy, l, r; big X, Y, Z, T;

bool check(long long a) { // is it in the circle
	if (a < 0) return 0;
	if (a > lim) return 0;
	return (sx + a * vx) * (sx + a * vx) + (sy + a * vy) * (sy + a * vy) <= R * R;
}

pair<long long, long long> p[200008];
vector<long long> tbc;

void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());}
int order(long long key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;}

int upd[400008];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, ans = 0, m = 0; cin >> n >> R;
	pair<long long, long long> range;
	for (int i = 1; i <= n; ++i) {
		cin >> sx >> sy >> sx2 >> sy2; vx = sx2 - sx; vy = sy2 - sy;
		X = vx * vx + vy * vy; Y = 2 * (sx * vx + sy * vy);
		Z = R * R - sx * sx - sy * sy; T = 4 * X * Z + Y * Y;
		if (T < 0) continue;
		l = (-Y - sqrtl(T)) / (2 * X); r = (-Y + sqrtl(T)) / (2 * X);
		l = max(l, 0LL); r = max(r, 0LL);
		range = {1, -1};
		for (long long i = l - 10; i <= l + 10; ++i) if (check(i)) {range.first = i; break;}
		for (long long i = r + 10; i >= r - 10; --i) if (check(i)) {range.second = i; break;}
		if (range.first <= range.second) {
			p[++m] = range;
			tbc.push_back(range.first); tbc.push_back(range.second);
		}
	}
	compress();
	for (int i = 1; i <= m; ++i) p[i].first = order(p[i].first), p[i].second = order(p[i].second);
	for (int i = 1; i <= m; ++i) ++upd[p[i].first], --upd[p[i].second + 1];
	for (int i = 1; i <= tbc.size() + 1; ++i) upd[i] += upd[i - 1];
	ans += *max_element(upd + 1, upd + tbc.size() + 1);
	cout << ans;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 1; i <= tbc.size() + 1; ++i) upd[i] += upd[i - 1];
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 23 / 23
• Subtask 3: 15 / 15
• Subtask 4: 32 / 32
• Subtask 5: 7 / 7