| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 912409 |
2024-01-19T12:09:07 Z |
vjudge1 |
Wish (LMIO19_noras) |
C++17 |
|
2 ms |
8796 KB |
// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int P = 18;
const int K = 800;
const ll INF = 2e18;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxm = 5e2+10;
const int maxn = 6e5+10;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll d[maxn];
int n, rd, sz;
map<ll, int>cnt;
int pref[maxn];
pair<ll, ll> get(ll l, ll r, int i){
if(l > r) return {-1, -1};
ll x = c[i]-a[i], y = d[i]-b[i], val=0;
if(abs(a[i]+x*l) > abs(a[i]+x*(l+1))) val -= abs(x);
else val += abs(x);
if(abs(b[i]+y*l) > abs(b[i]+y*(l+1))) val -= abs(y);
else val += abs(y);
ll sum = abs(a[i]+x*l) + abs(b[i]+y*l);
ll L = -1, R = -1;
if(val < 0){
for(ll l1=l, r1=r; l1<=r1;){
ll mid = l1+r1>>1;
if(sum+val*(mid-l) > rd) l1 = mid + 1;
else r1 = mid - 1, L = mid;
} if(L == -1) return {-1, -1};
for(ll l1=l, r1=r; l1<=r1;){
ll mid = l1+r1>>1;
if(sum+val*(mid-l) < -rd) r1 = mid - 1;
else l1 = mid + 1, R = mid;
} if(R == -1) return {-1, -1};
return {L, R};
}
for(ll l1=l, r1=r; l1<=r1;){
ll mid = l1+r1>>1;
if(sum+val*(mid-l) < -rd) l1 = mid + 1;
else r1 = mid - 1, L = mid;
} if(L == -1) return {-1, -1};
for(ll l1=l, r1=r; l1<=r1;){
ll mid = l1+r1>>1;
if(sum+val*(mid-l) > rd) r1 = mid - 1;
else l1 = mid + 1, R = mid;
} if(R == -1 || L > R) return {-1, -1};
return {L, R};
}
ll firt(ll x, ll c){
return abs(x)/abs(c);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
vector<pair<ll, ll>>v;
cin >> n >> rd;
for(int i=1; i<=n; i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
ll x = c[i]-a[i], y = d[i]-b[i];
if(a[i]*x < 0 && b[i]*y < 0){
ll mn = min(firt(a[i], x), firt(b[i], y));
ll mx = max(firt(a[i], x), firt(b[i], y));
v.pb(get(0, mn, i));
v.pb(get(mn+1, mx, i));
v.pb(get(mx+1, 1e9, i));
} else if(a[i]*x < 0){
ll mn = firt(a[i], x);
v.pb(get(0, mn, i));
v.pb(get(mn+1, 1e9, i));
} else if(b[i]*y < 0){
ll mn = firt(b[i], y);
v.pb(get(0, mn, i));
v.pb(get(mn+1, 1e9, i));
} else{
v.pb(get(0, 1e18, i));
}
}
set<ll>st;
for(auto to: v){
if(to.f == -1) continue;
st.insert(to.f);
st.insert(to.s);
}
for(auto to: st) cnt[to] = ++sz;
for(auto to: v){
if(to.f == -1) continue;
pref[cnt[to.f]]++;
pref[cnt[to.s]+1]--;
} int ans = 0;
for(int i=0; i<=sz; i++){
if(i) pref[i] += pref[i-1];
ans = max(ans, pref[i]);
} cout << ans;
}
Compilation message
noras.cpp: In function 'std::pair<long long int, long long int> get(ll, ll, int)':
noras.cpp:43:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | ll mid = l1+r1>>1;
| ~~^~~
noras.cpp:48:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | ll mid = l1+r1>>1;
| ~~^~~
noras.cpp:55:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | ll mid = l1+r1>>1;
| ~~^~~
noras.cpp:60:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | ll mid = l1+r1>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
