oj.uz

Submission #626610

# Submission time Handle Problem Language Result Execution time Memory
626610 2022-08-11T15:04:29 Z mkisic Wish (LMIO19_noras) C++14
100 / 100
 503 ms 11352 KB 
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

#define X first
#define Y second

typedef long long ll;
typedef pair<long long, long long> pii;

const int MAXN = 2e5 + 5;
const ll INF = (1LL << 60) + 5;
const ll INF_binary = (1 << 30);

int n;
ll R;
vector<pii> dogadaji;

double udaljenost(pii T) { return sqrt((double)T.X * T.X + (double)T.Y * T.Y); }

pii izracunaj_tocku(ll x, ll y, ll sx, ll sy, ll t) {
  ll x2 = min(INF, x + t * sx);
  ll y2 = min(INF, y + t * sy);
  // cerr << x2 << ' ' << y2 << '\n';
  return {x2, y2};
}

void dodaj_tocku() {
  ll x, y, sx, sy;
  cin >> x >> y >> sx >> sy;

  sx -= x;
  sy -= y;

  // cerr << '\n' << x << ' ' << y << " : " << sx << ' ' << sy << '\n';

  ll l = 0, r = INF_binary, m1, m2;

  while (r - l >= 3) {
    m1 = l + (r - l) / 3;
    m2 = r - (r - l) / 3;

    double d1 = udaljenost(izracunaj_tocku(x, y, sx, sy, m1));
    double d2 = udaljenost(izracunaj_tocku(x, y, sx, sy, m2));

    // cerr << l << ' ' << r << " : " << m1 << ' ' << m2 << " : " << d1 << ' '
    // << d2 << '\n';

    if (d1 < d2)
      r = m2;
    else
      l = m1;
  }

  for (int i = l + 1; i <= r; i++) {
    if (udaljenost(izracunaj_tocku(x, y, sx, sy, l)) >
        udaljenost(izracunaj_tocku(x, y, sx, sy, i)))
      l = i;
  }

  pii sredina = izracunaj_tocku(x, y, sx, sy, l);
  ll xx = sredina.X;
  ll yy = sredina.Y;

  // cerr << "sredina " << l << " : " << xx << ' ' << yy;
  // cerr << " : " << udaljenost({xx, yy}) << ' ' << r << '\n';

  if (udaljenost({xx, yy}) > R)
    return;

  ll lo = 0, hi = l, mid;

  while (lo < hi) {
    mid = (lo + hi) / 2;

    double d = udaljenost(izracunaj_tocku(x, y, sx, sy, mid));

    // cerr << lo << ' ' << hi << " : " << mid << ' ' << d << ' ' << R << '\n';

    if (d <= R)
      hi = mid;
    else
      lo = mid + 1;
  }

  ll t1 = lo;

  lo = l, hi = INF_binary;

  while (lo < hi) {
    mid = (lo + hi) / 2 + 1;

    double d = udaljenost(izracunaj_tocku(x, y, sx, sy, mid));

    if (d <= R)
      lo = mid;
    else
      hi = mid - 1;
  }

  ll t2 = lo;

  // cerr << t1 << ' ' << t2 << '\n';

  dogadaji.push_back({t1 * 2, +1});
  dogadaji.push_back({t2 * 2 + 1, -1});
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> R;

  for (int i = 0; i < n; i++) {
    dodaj_tocku();
  }

  int maks = 0;
  int trenutno = 0;

  sort(dogadaji.begin(), dogadaji.end());

  // cerr << '\n';

  for (auto nx : dogadaji) {
    trenutno += nx.Y;
    maks = max(maks, trenutno);
  }

  cout << maks << '\n';

  return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 207 ms 4560 KB Output is correct
24 Correct 196 ms 4596 KB Output is correct
25 Correct 230 ms 4552 KB Output is correct
26 Correct 191 ms 4584 KB Output is correct
27 Correct 166 ms 2412 KB Output is correct
28 Correct 222 ms 4440 KB Output is correct
29 Correct 196 ms 4500 KB Output is correct
30 Correct 197 ms 4540 KB Output is correct
31 Correct 195 ms 4484 KB Output is correct
32 Correct 224 ms 4496 KB Output is correct
33 Correct 213 ms 4508 KB Output is correct
34 Correct 217 ms 4524 KB Output is correct
35 Correct 243 ms 5856 KB Output is correct
36 Correct 223 ms 5928 KB Output is correct
37 Correct 202 ms 4028 KB Output is correct
38 Correct 186 ms 3992 KB Output is correct
39 Correct 168 ms 4000 KB Output is correct
40 Correct 194 ms 3836 KB Output is correct
41 Correct 180 ms 3908 KB Output is correct
42 Correct 179 ms 4112 KB Output is correct
43 Correct 478 ms 11304 KB Output is correct
44 Correct 503 ms 11308 KB Output is correct
45 Correct 477 ms 11328 KB Output is correct
46 Correct 449 ms 11352 KB Output is correct
47 Correct 467 ms 11268 KB Output is correct
48 Correct 413 ms 11132 KB Output is correct
49 Correct 438 ms 11120 KB Output is correct
50 Correct 412 ms 11184 KB Output is correct
51 Correct 424 ms 11168 KB Output is correct
52 Correct 420 ms 11296 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 388 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 3 ms 332 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 207 ms 4560 KB Output is correct
24 Correct 196 ms 4596 KB Output is correct
25 Correct 230 ms 4552 KB Output is correct
26 Correct 191 ms 4584 KB Output is correct
27 Correct 166 ms 2412 KB Output is correct
28 Correct 222 ms 4440 KB Output is correct
29 Correct 196 ms 4500 KB Output is correct
30 Correct 197 ms 4540 KB Output is correct
31 Correct 195 ms 4484 KB Output is correct
32 Correct 224 ms 4496 KB Output is correct
33 Correct 213 ms 4508 KB Output is correct
34 Correct 217 ms 4524 KB Output is correct
35 Correct 243 ms 5856 KB Output is correct
36 Correct 223 ms 5928 KB Output is correct
37 Correct 202 ms 4028 KB Output is correct
38 Correct 186 ms 3992 KB Output is correct
39 Correct 168 ms 4000 KB Output is correct
40 Correct 194 ms 3836 KB Output is correct
41 Correct 180 ms 3908 KB Output is correct
42 Correct 179 ms 4112 KB Output is correct
43 Correct 478 ms 11304 KB Output is correct
44 Correct 503 ms 11308 KB Output is correct
45 Correct 477 ms 11328 KB Output is correct
46 Correct 449 ms 11352 KB Output is correct
47 Correct 467 ms 11268 KB Output is correct
48 Correct 413 ms 11132 KB Output is correct
49 Correct 438 ms 11120 KB Output is correct
50 Correct 412 ms 11184 KB Output is correct
51 Correct 424 ms 11168 KB Output is correct
52 Correct 420 ms 11296 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 2 ms 340 KB Output is correct
55 Correct 3 ms 340 KB Output is correct
56 Correct 2 ms 388 KB Output is correct
57 Correct 2 ms 340 KB Output is correct
58 Correct 3 ms 332 KB Output is correct
59 Correct 204 ms 5808 KB Output is correct
60 Correct 168 ms 4176 KB Output is correct
61 Correct 165 ms 4012 KB Output is correct
62 Correct 173 ms 4100 KB Output is correct
63 Correct 177 ms 4112 KB Output is correct
64 Correct 175 ms 4184 KB Output is correct
65 Correct 172 ms 4108 KB Output is correct
66 Correct 180 ms 4180 KB Output is correct
67 Correct 180 ms 4100 KB Output is correct
68 Correct 210 ms 6020 KB Output is correct
69 Correct 214 ms 5980 KB Output is correct
70 Correct 217 ms 6008 KB Output is correct
71 Correct 204 ms 6020 KB Output is correct
72 Correct 226 ms 6020 KB Output is correct
73 Correct 172 ms 3844 KB Output is correct
74 Correct 179 ms 6080 KB Output is correct
75 Correct 186 ms 6084 KB Output is correct
76 Correct 177 ms 4112 KB Output is correct
77 Correct 418 ms 10836 KB Output is correct
78 Correct 416 ms 11216 KB Output is correct
79 Correct 426 ms 10664 KB Output is correct
80 Correct 428 ms 10672 KB Output is correct
81 Correct 412 ms 10704 KB Output is correct
82 Correct 443 ms 10832 KB Output is correct
83 Correct 437 ms 10564 KB Output is correct
84 Correct 414 ms 10560 KB Output is correct
85 Correct 437 ms 10320 KB Output is correct
86 Correct 435 ms 10736 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 207 ms 4560 KB Output is correct
24 Correct 196 ms 4596 KB Output is correct
25 Correct 230 ms 4552 KB Output is correct
26 Correct 191 ms 4584 KB Output is correct
27 Correct 166 ms 2412 KB Output is correct
28 Correct 222 ms 4440 KB Output is correct
29 Correct 196 ms 4500 KB Output is correct
30 Correct 197 ms 4540 KB Output is correct
31 Correct 195 ms 4484 KB Output is correct
32 Correct 224 ms 4496 KB Output is correct
33 Correct 213 ms 4508 KB Output is correct
34 Correct 217 ms 4524 KB Output is correct
35 Correct 243 ms 5856 KB Output is correct
36 Correct 223 ms 5928 KB Output is correct
37 Correct 202 ms 4028 KB Output is correct
38 Correct 186 ms 3992 KB Output is correct
39 Correct 168 ms 4000 KB Output is correct
40 Correct 194 ms 3836 KB Output is correct
41 Correct 180 ms 3908 KB Output is correct
42 Correct 179 ms 4112 KB Output is correct
43 Correct 478 ms 11304 KB Output is correct
44 Correct 503 ms 11308 KB Output is correct
45 Correct 477 ms 11328 KB Output is correct
46 Correct 449 ms 11352 KB Output is correct
47 Correct 467 ms 11268 KB Output is correct
48 Correct 413 ms 11132 KB Output is correct
49 Correct 438 ms 11120 KB Output is correct
50 Correct 412 ms 11184 KB Output is correct
51 Correct 424 ms 11168 KB Output is correct
52 Correct 420 ms 11296 KB Output is correct
53 Correct 204 ms 5808 KB Output is correct
54 Correct 168 ms 4176 KB Output is correct
55 Correct 165 ms 4012 KB Output is correct
56 Correct 173 ms 4100 KB Output is correct
57 Correct 177 ms 4112 KB Output is correct
58 Correct 175 ms 4184 KB Output is correct
59 Correct 172 ms 4108 KB Output is correct
60 Correct 180 ms 4180 KB Output is correct
61 Correct 180 ms 4100 KB Output is correct
62 Correct 210 ms 6020 KB Output is correct
63 Correct 214 ms 5980 KB Output is correct
64 Correct 217 ms 6008 KB Output is correct
65 Correct 204 ms 6020 KB Output is correct
66 Correct 226 ms 6020 KB Output is correct
67 Correct 172 ms 3844 KB Output is correct
68 Correct 179 ms 6080 KB Output is correct
69 Correct 186 ms 6084 KB Output is correct
70 Correct 177 ms 4112 KB Output is correct
71 Correct 418 ms 10836 KB Output is correct
72 Correct 416 ms 11216 KB Output is correct
73 Correct 426 ms 10664 KB Output is correct
74 Correct 428 ms 10672 KB Output is correct
75 Correct 412 ms 10704 KB Output is correct
76 Correct 443 ms 10832 KB Output is correct
77 Correct 437 ms 10564 KB Output is correct
78 Correct 414 ms 10560 KB Output is correct
79 Correct 437 ms 10320 KB Output is correct
80 Correct 435 ms 10736 KB Output is correct
81 Correct 0 ms 212 KB Output is correct
82 Correct 2 ms 340 KB Output is correct
83 Correct 3 ms 340 KB Output is correct
84 Correct 2 ms 388 KB Output is correct
85 Correct 2 ms 340 KB Output is correct
86 Correct 3 ms 332 KB Output is correct
87 Correct 199 ms 4588 KB Output is correct
88 Correct 198 ms 4528 KB Output is correct
89 Correct 183 ms 4516 KB Output is correct
90 Correct 190 ms 4624 KB Output is correct
91 Correct 187 ms 4628 KB Output is correct
92 Correct 196 ms 4480 KB Output is correct
93 Correct 189 ms 4624 KB Output is correct
94 Correct 188 ms 4544 KB Output is correct
95 Correct 188 ms 4500 KB Output is correct
96 Correct 214 ms 4432 KB Output is correct
97 Correct 221 ms 6280 KB Output is correct
98 Correct 240 ms 6304 KB Output is correct
99 Correct 219 ms 6220 KB Output is correct
100 Correct 212 ms 6300 KB Output is correct
101 Correct 205 ms 6288 KB Output is correct
102 Correct 213 ms 6264 KB Output is correct
103 Correct 226 ms 6204 KB Output is correct
104 Correct 200 ms 6212 KB Output is correct
105 Correct 201 ms 6308 KB Output is correct
106 Correct 202 ms 6280 KB Output is correct