| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 487425 |
2021-11-15T13:17:35 Z |
idas |
Wish (LMIO19_noras) |
C++17 |
|
0 ms |
204 KB |
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define sz(x) int((x).size())
using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
const int INF=1e9, MOD=1e9+7, mod=98244353;
const long long LINF=1e5, LIMIT=1e9+99999999;
void setIO()
{
FAST_IO;
}
void setIO(string s)
{
FAST_IO;
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
const int N=2e5+10;
ll n, R;
pair<ll, ll> ini[N], add[N];
ll sq(ll x){return x*x;}
pair<ll, ll> getPos(int in, ll t)
{
return {ini[in].F+add[in].F*t, ini[in].S+add[in].S*t};
}
ll calcDist(pair<ll, ll> pos)
{
if(pos.F<0||pos.S<0||pos.F>LIMIT||pos.S>LIMIT){
return -1;
}
return sq(pos.F)+sq(pos.S);
}
ll getLow(int in)
{
//davai patikrini po to shita shuda
ll l=-1, r=INF;
while(l<r-1){
ll m1=(l+r)/2, m2=m1+1;
pair<ll, ll> pos1=getPos(in, m1), pos2=getPos(in, m2);
ll v1=calcDist(pos1), v2=calcDist(pos2);
if(v1<0||v2<0){
r=m1;
continue;
}
if(v1<=v2) r=m1;
else l=m1;
}
return l+1;
}
ll lbound(int in, ll x)
{
ll l=0, r=x;
while(l<r){
ll m=(l+r)/2;
pair<ll, ll> pos=getPos(in, m); ll dist=calcDist(pos);
if(dist<0){
r=m;
continue;
}
if(dist>R*R) l=m+1;
else r=m;
}
return l;
}
ll rbound(int in, ll x)
{
ll l=x, r=INF;
while(l<r){
ll m=(l+r+1)/2;
pair<ll, ll> pos=getPos(in, m); ll dist=calcDist(pos);
if(dist<0){
r=m-1;
continue;
}
if(dist>R*R) r=m-1;
else l=m;
}
return l;
}
int main()
{
setIO();
cin >> n >> R;
ll now=0;
FOR(i, 0, n)
{
ll aa, bb, cc, dd;
cin >> aa >> bb >> cc >> dd;
ini[i]={aa, bb}; add[i]={cc-aa, dd-bb};
}
vector<pair<ll, int>> inf;
FOR(i, 0, n)
{
ll low=getLow(i);
pair<ll, ll> pos=getPos(i, low); ll dist=calcDist(pos);
if(dist<0||dist>R*R) continue;
int l=lbound(i, low), r=rbound(i, low);
inf.PB({l, 1}); inf.PB({r+1, -1});
}
sort(inf.begin(), inf.end());
ll ans=0;
for(auto[x, y] : inf){
now+=y;
ans=max(ans, now);
}
cout << ans;
}
/*
TESTINGAS:
3 1
0 0 100000 0
0 0 0 0
0 0 0 0
*/
Compilation message
noras.cpp: In function 'void setIO(std::string)':
noras.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
noras.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
