oj.uz

Submission #965293

# Submission time Handle Problem Language Result Execution time Memory
965293 2024-04-18T09:45:39 Z AtabayRajabli Wish (LMIO19_noras) C++17
0 / 100
 2 ms 500 KB 
#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#define GCD(a, b)   __gcd(a, b)
#define LCM(a, b)   (a*b / (__gcd(a, b)))
#define int         ll

typedef long long           ll;
typedef long double         ld;
const int inf =             1e9 + 7;
const int inff =            (int)1e18 + 7;
const int sz =              2e5 + 5;
using namespace             std;

int n;
ld r;
vector<array<int, 2>> v;

ld sqr(__int128 x)
{
    ld l = 0, r = 4000000000;
    while(r - l >= 0.0000001)
    {
        ld m = (l + r) / 2.0;
        if(m <= x / m)l = m + 0.0000001;
        else r = m - 0.0000001;
    }
    return l - 0.0000001;
}

signed main()   
{       
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> r;
    
    for(int i = 1; i <= n; i++)
    {
        ld x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x2 -= x1;
        y2 -= y1;
        ld a = x2 * x2 + y2 * y2;
        __int128 b = 2 * (x1 * x2 + y1 * y2);
        ld c = x1 * x1 + y1 * y1 - r * r;
        __int128 d = b * b - 4 * a * c;
        if(d < 0)continue;
        ld x = (- b - sqr(d)) / (2.0 * a);
        ld y = (- b + sqr(d)) / (2.0 * a);
        int xi = ceil(x);
        int yi = floor(y);
        if(xi > yi || yi < 0LL)continue;
        v.push_back({max(xi, 0LL), 1});
        v.push_back({yi + 1, -1});
    }

    int s = 0, mx = 0;
    sort(all(v));
    for(auto i : v)
    {
        s += i[1];
        mx = max(mx, s);
    }
    cout << mx;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 360 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 376 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Incorrect 2 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 360 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 376 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Incorrect 2 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 360 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 376 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Incorrect 2 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 360 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 376 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Incorrect 2 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 360 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 376 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Incorrect 2 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -