#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3MJnHrA ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
// kactl line container
// cht on max point
// use monotocity if possible
// o(nlgn)
// APIO'10 P1
// DMOJ Yet Another Contest 2 P6 - Travel Budget
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
using T=pair<int,pair<pii,pii>>;
using Q=pair<int,pii>;
const int inf=1e15;
signed main(){
_3MJnHrA;
int n,q;
cin>>n>>q;
vec(T) a(n);
rep(i,n){
int _t,_l,_r,_c;
cin>>_t>>_l>>_r>>_c;
pii s={_t,_l};
pii t={_t+abs(_r-_l),_r};
s={s.fi-s.se,s.fi+s.se};
t={t.fi-t.se,t.fi+t.se};
a[i]=T(_c,{s,t});
}
assert(q>40000);
vi xys={inf};
rep(i,n){
pii s=a[i].se.fi,t=a[i].se.se;
// print(s.fi,s.se,t.fi,t.se);
xys.pb(s.fi);
xys.pb(s.se);
xys.pb(t.fi);
xys.pb(t.se);
}
sort(xys.begin(), xys.end());
xys.erase(unique(xys.begin(), xys.end()),xys.end());
auto ced=[&](int x){
return (int)(lower_bound(xys.begin(), xys.end(),x)-xys.begin());
};
int _n=sz(xys);
vec(vi) movex(_n,vi(_n)),movey;
movey=movex;
{
rep(i,n){
int cosu=a[i].fi;
pii s=a[i].se.fi,t=a[i].se.se;
int type=s.fi==t.fi;
s.fi=ced(s.fi);
s.se=ced(s.se);
t.fi=ced(t.fi);
t.se=ced(t.se);
// print(s.fi,s.se,t.fi,t.se);
if(type){
rng(j,s.se,t.se){
movey[s.fi][j]=max(movey[s.fi][j],cosu);
}
}else{
rng(j,s.fi,t.fi){
movex[j][s.se]=max(movex[j][s.se],cosu);
}
}
}
}
vec(vi) dp(_n,vi(_n));
per(i,_n){
per(j,_n){
if(i+1<_n){
dp[i][j]=max(dp[i][j],dp[i+1][j]+(xys[i+1]-xys[i])*movex[i][j]);
}
if(j+1<_n){
dp[i][j]=max(dp[i][j],dp[i][j+1]+(xys[j+1]-xys[j])*movey[i][j]);
}
}
}
vi pns(q);
vec(vec(Q)) adqry_y(_n),adqry_x;
adqry_x=adqry_y;
rep(i,q){
int t,_x;
cin>>t>>_x;
pii p={t-_x,t+_x};
int x=p.fi,y=p.se;
p.fi=ced(p.fi);
p.se=ced(p.se);
pns[i]=max(pns[i],dp[p.fi][p.se]);
if(p.se){
adqry_y[p.se].pb({p.fi,{y,i}});
}
if(p.fi){
adqry_x[p.fi].pb({p.se,{x,i}});
}
// if(p.se){
// rng(i,p.fi,_n){
// ans=max(ans,dp[i][p.se]+movey[i][p.se-1]*(xys[p.se]-y));
// }
// }
// if(p.fi){
// rng(j,p.se,_n){
// ans=max(ans,dp[p.fi][j]+movex[p.fi-1][j]*(xys[p.fi]-x));
// }
// }
}
rng(i,1,_n){
sort(adqry_x[i].begin(),adqry_x[i].end());
LineContainer cht;
cht.add(0,0);
per(j,_n){
cht.add(-movex[i-1][j],movex[i-1][j]*xys[i]+dp[i][j]);
while(sz(adqry_x[i])){
Q p=adqry_x[i].back();
if(p.fi>=j){
// print(p.se.fi,"ho");
pns[p.se.se]=max(pns[p.se.se],cht.query(p.se.fi));
adqry_x[i].pop_back();
}else{
break;
}
}
}
}
rng(j,1,_n){
sort(adqry_y[j].begin(),adqry_y[j].end());
LineContainer cht;
cht.add(0,0);
per(i,_n){
cht.add(-movey[i][j-1],movey[i][j-1]*xys[j]+dp[i][j]);
while(sz(adqry_y[j])){
Q p=adqry_y[j].back();
if(p.fi>=i){
// print(p.se.fi,"ho",cht.query(p.se.fi));
pns[p.se.se]=max(pns[p.se.se],cht.query(p.se.fi));
adqry_y[j].pop_back();
}else{
break;
}
}
}
}
rep(i,q){
assert(pns[i]%2==0);
cout<<pns[i]/2<<"\n";
}
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6019 ms |
886624 KB |
Output is correct |
| 2 |
Correct |
6170 ms |
919592 KB |
Output is correct |
| 3 |
Correct |
2801 ms |
399984 KB |
Output is correct |
| 4 |
Correct |
3052 ms |
434100 KB |
Output is correct |
| 5 |
Correct |
7788 ms |
1337012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6019 ms |
886624 KB |
Output is correct |
| 2 |
Correct |
6170 ms |
919592 KB |
Output is correct |
| 3 |
Correct |
2801 ms |
399984 KB |
Output is correct |
| 4 |
Correct |
3052 ms |
434100 KB |
Output is correct |
| 5 |
Correct |
7788 ms |
1337012 KB |
Output is correct |
| 6 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
