//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "shortcut.h"
const int maxn = 3e3+10;
ll pos[maxn];
ll a[maxn];
int n;
ll C;
ll tree[2][maxn*maxn*4],add[maxn*maxn*4];
set <ll> p;
vector <pii> tmp;
void init (int c,int cl,int cr,ll d) {
add[c] = 0;
if (cl==cr) {
int l = tmp[cl].fi, r = tmp[cl].se;
tree[0][c] = pos[r]-(d-pos[l]-a[l]-a[r]);
tree[1][c] = pos[r]+(d-pos[l]-a[l]-a[r]);
// debug(pos[r]);
// debug(pos[l]);
// debug(tree[0][c]),debug(tree[1][c]);
}
else {
int mid=cl+cr>>1;
init(c<<1,cl,mid,d);
init(c<<1|1,mid+1,cr,d);
tree[0][c] = max(tree[0][c<<1],tree[0][c<<1|1]);
tree[1][c] = min(tree[1][c<<1],tree[1][c<<1|1]);
}
}
void update(int c,int cl,int cr,int l,int r,ll val) {
if (l>r) return;
if (l<=cl and cr<=r) {
tree[0][c] -= val;
tree[1][c] += val;
add[c]+=val;
// debug(val);
// cout<<cl<<" "<<tree[0][c]<<" "<<tree[1][c]<<endl;
return;
}
if (add[c]!=0) {
tree[0][c<<1] -= add[c];
tree[0][c<<1|1] -= add[c];
tree[1][c<<1] += add[c];
tree[1][c<<1|1] += add[c];
add[c<<1] += add[c];
add[c<<1|1] += add[c];
add[c] = 0;
}
int mid=cl+cr>>1;
if (l<=mid) update(c<<1,cl,mid,l,r,val);
if (r>mid) update(c<<1|1,mid+1,cr,l,r,val);
tree[0][c] = max(tree[0][c<<1],tree[0][c<<1|1]);
tree[1][c] = min(tree[1][c<<1],tree[1][c<<1|1]);
}
bool check(ll d) {
tmp.clear();
rep(i,0,n)
rep(j,i+1,n) {
if (pos[j]-pos[i]+a[i]+a[j]>d) {
if (d<C) return false;
tmp.pb({i,j});
}
}
if (tmp.empty()) return true;
// debug(d),debug(SZ(tmp));
// for (auto it:tmp) debug(it.fi),debug(it.se);
d -= C;
init(1,0,SZ(tmp)-1,d);
if (tree[0][1]<=tree[1][1] and (*p.lower_bound(tree[0][1])) < tree[1][1]) return true;
int cur = 0;
rep(i,1,n) {
while (cur<SZ(tmp) and tmp[cur].fi<i) cur++;
update(1,0,SZ(tmp)-1,0,cur-1,-pos[i]+pos[i-1]);
update(1,0,SZ(tmp)-1,cur,SZ(tmp)-1,pos[i]-pos[i-1]);
if (tree[0][1]<=tree[1][1] and (*p.lower_bound(tree[0][1])) < tree[1][1]) return true;
}
return false;
}
long long find_shortcut(int N, std::vector<int> L, std::vector<int> d, int c)
{
p.clear();
n = N; C=c;
pos[0] = 0;
p.insert(0);
rep(i,1,n) pos[i] = pos[i-1] + L[i-1],p.insert(pos[i]);
rep(i,0,n) a[i] = d[i];
ll l = 0,r = 1e16;
while (l<r) {
ll mid = (l+r)/2;
if (check(mid)) r = mid;
else l = mid+1;
}
return l;
}
Compilation message
shortcut.cpp: In function 'void init(int, int, int, long long int)':
shortcut.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid=cl+cr>>1;
| ~~^~~
shortcut.cpp: In function 'void update(int, int, int, int, int, long long int)':
shortcut.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int mid=cl+cr>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 81 |
| 2 |
Halted |
0 ms |
0 KB |
- |
