#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct line { ll a,b; bool is = 1; ll operator()(ll x) { if(is == 0) return -5e18; return a*x+b; } }; struct lichao { ll l = -((1LL << 32LL)); ll r = (1LL << 32LL)-1; line best = {(ll)-1e18-2137,(ll)-1e18,0}; lichao* left = NULL; lichao* right = NULL; void add_line(line line) { if(best.is == 0) { best = line; return; } ll mid = (l+r)/2; if(line(mid) > best(mid)) swap(best,line); if(l == r) return; if(line.a < best.a) { if(left == NULL) { left = new lichao; left -> l = l; left -> r = mid-1; } if(left -> l <= left -> r) { left -> add_line(line); } } else { if(right == NULL) { right = new lichao; right -> l = mid+1; right -> r = r; } if(right -> l <= right -> r) { right -> add_line(line); } } } ll get_val(ll x) { if(x <= (l+r)/2) return max((ll)best(x),(left != NULL ? left -> get_val(x) : (ll)-3e18)); else return max((ll)best(x),(right != NULL ? right -> get_val(x) : (ll)-3e18)); } }; struct seg { pll p1,p2; ll c; bool t; }; struct event { ll x,y,type,ind; bool operator<(const event& other) { if(y != other.y) return y > other.y; return type < other.type; } }; pll rotate(ll t, ll p) { return {t+p,t-p}; } vector<seg> segs; vector<int> segs_p[2801]; vector<pll> points; ll dist[24000000]; ll query_ans[3000001]; vector<pll> graph[24000001]; vi graph2[20000001]; int cur_p = 0; vector<pair<pll,int>> queries; int cur_line[2801]; int n,q; void solve2(vector<pair<pll,int>>& q2,vi& s) { sort(all(q2)); reverse(all(q2)); lichao tree_; int cur = 0; forall(it,q2) { while(cur < siz(s) && segs[s[cur]].p1.ff >= it.ff.ff) { if(cur_line[s[cur]] != siz(segs_p[s[cur]])) { tree_.add_line({-(cur_line[s[cur]] != 0 ? segs[s[cur]].c : 0),dist[segs_p[s[cur]][cur_line[s[cur]]]]+(cur_line[s[cur]] != 0 ? segs[s[cur]].c : 0)*points[segs_p[s[cur]][cur_line[s[cur]]]].ss}); } cur++; } query_ans[it.ss] = max(query_ans[it.ss],tree_.get_val(it.ff.ss)); } } void solve() { rep(i,n) cur_line[i] = siz(segs_p[i]); vector<event> events; vector<pair<pll,int>> q2; vector<pii> vs; rep(i,n) if(segs[i].t) vs.pb({segs[i].p1.ff,i}); sort(all(vs)); reverse(all(vs)); vi s; rep(i,siz(vs)) s.pb(vs[i].ss); rep(i,n) { if(segs[i].t) { forall(it,segs_p[i]) events.pb({points[it].ff,points[it].ss,0,i}); } } forall(it,queries) events.pb({it.ff.ff,it.ff.ss,1,it.ss}); sort(all(events)); forall(it,events) { if(it.type == 0) { solve2(q2,s); q2 = {}; cur_line[it.ind]--; } else { q2.pb({{it.x,it.y},it.ind}); } } solve2(q2,s); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); cin >> n >> q; rep(i,n) { ll t,a,b,c; cin >> t >> a >> b >> c; segs.pb({rotate(t,a),rotate(t+abs(a-b),b),c,a>b}); } rep(i,n) { points.pb(segs[i].p1); segs_p[i].pb(cur_p++); points.pb(segs[i].p2); segs_p[i].pb(cur_p++); } rep(i,n) { rep(j,n) { if(segs[i].t == 0 && segs[j].t == 1) { if(segs[i].p1.ff <= segs[j].p1.ff && segs[i].p2.ff >= segs[j].p1.ff && segs[i].p1.ss <= segs[j].p2.ss && segs[i].p2.ss >= segs[j].p1.ss) { points.pb({segs[j].p1.ff,segs[i].p1.ss}); segs_p[i].pb(cur_p); segs_p[j].pb(cur_p++); } } if(segs[j].p1.ff >= segs[i].p1.ff && segs[j].p1.ss >= segs[i].p1.ss) { if(segs[i].t == 0) { points.pb({min(segs[j].p1.ff,segs[i].p2.ff),segs[i].p1.ss}); graph2[cur_p].pb(j*2); segs_p[i].pb(cur_p++); } else { points.pb({segs[i].p2.ff,min(segs[i].p2.ss,segs[j].p1.ss)}); graph2[cur_p].pb(j*2); segs_p[i].pb(cur_p++); } } if(segs[j].p2.ff >= segs[i].p2.ff && segs[j].p2.ss >= segs[i].p2.ss) { if(segs[j].t == 0) { points.pb({max(segs[j].p1.ff,segs[i].p2.ff),segs[j].p1.ss}); graph2[i*2+1].pb(cur_p); segs_p[j].pb(cur_p++); } else { points.pb({segs[j].p1.ff,max(segs[j].p1.ss,segs[i].p2.ss)}); graph2[i*2+1].pb(cur_p); segs_p[j].pb(cur_p++); } } } } vector<pair<pll,int>> vs; map<int,int> m; rep(i,siz(points)) vs.pb({points[i],i}); sort(all(vs)); int sp = siz(points); points = {}; int cur = -1; pll pop = {-1e11,-1e11}; forall(it,vs) { if(pop.ff != it.ff.ff || pop.ss != it.ff.ss) { cur++; points.pb(it.ff); } m[it.ss] = cur; pop = it.ff; } rep(i,sp) { forall(it,graph2[i]) { graph[m[i]].pb({m[it],0}); } } rep(i,n) forall(it,segs_p[i]) it = m[it]; rep(i,n) { set<int> x; forall(it,segs_p[i]) x.insert(it); segs_p[i] = {}; forall(it,x) segs_p[i].pb(it); int pop = -1; ll pop_poz = 0; forall(it,segs_p[i]) { ll my_poz = points[it].ff; if(segs[i].t == 1) my_poz = points[it].ss; if(pop != -1) graph[pop].pb({it,(my_poz-pop_poz)*segs[i].c}); pop = it; pop_poz = my_poz; } } for(int i = siz(points)-1; i >= 0; i--) { dist[i] = 0; forall(it,graph[i]) { dist[i] = max(dist[i],it.ss+dist[it.ff]); } } rep(qq,q) { ll t,p; cin >> t >> p; queries.pb({rotate(t,p),qq}); } solve(); rep(i,siz(points)) swap(points[i].ff,points[i].ss); rep(i,q) swap(queries[i].ff.ff,queries[i].ff.ss); rep(i,n) { swap(segs[i].p1.ff,segs[i].p1.ss); swap(segs[i].p2.ff,segs[i].p2.ss); segs[i].t ^= 1; } solve(); rep(qq,q) cout << query_ans[qq]/2 << "\n"; }

bodyguard.cpp: In function 'void solve()':
bodyguard.cpp:177:35: warning: narrowing conversion of 'it.event::ind' from 'long long int' to 'int' [-Wnarrowing]
  177 |             q2.pb({{it.x,it.y},it.ind});
      |                                ~~~^~~