oj.uz

Submission #1016023

# Submission time Handle Problem Language Result Execution time Memory
1016023 2024-07-07T09:58:31 Z vjudge1 Wish (LMIO19_noras) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
#define big __int128_t

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

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;
	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;
		l = (Y - sqrtl(T)) / (2 * X); r = (Y + sqrtl(T)) / (2 * X);
		range = {1, -1};
		for (long long i = l - 12; i <= l + 12; ++i) if (check(i)) {range.first = i; break;}
		for (long long i = r + 12; i >= r - 12; --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(); ++i) upd[i] += upd[i - 1];
	ans += *max_element(upd + 1, upd + tbc.size() + 1);
	cout << ans;
}

Compilation message

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

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -