Submission #1196377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196377		byunjaewoo	Bodyguard (JOI21_bodyguard)	C++20	0 / 100	3199 ms	401040 KiB

bodyguard

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=2810, Q=3000010, S=1e9, INF=1e18;
int n, q, t[N], a[N], b[N], c[N], p[Q], x[Q], ans[Q], dp[2*N][2*N], lv[2*N][2*N], uv[2*N][2*N];
vector<int> cx, cy;
vector<pair<int, int>> vec1[2*N], vec2[2*N];

class LiChao {
public:
    LiChao() {root=new Node();}
    void update(int a, int b) {update(root, -S, S, {a, b});}
    int query(int x) {return query(root, -S, S, x);}
    void clear() {root=new Node();}
private:
    struct Node {
        Node *l, *r;
        array<int, 2> v;
        Node() {l=r=NULL; v={0, -INF};}
    };
    Node *root;
    void update(Node *curr, int s, int e, array<int, 2> v) {
        if(curr->v[0]*s+curr->v[1]<v[0]*s+v[1]) swap(curr->v, v);
        if(curr->v[0]*e+curr->v[1]>=v[0]*e+v[1]) return;
        int m=(s+e)/2;
        if(curr->v[0]*m+curr->v[1]>=v[0]*m+v[1]) {
            if(!curr->r) curr->r=new Node();
            update(curr->r, m+1, e, v);
        }
        else {
            swap(v, curr->v);
            if(!curr->l) curr->l=new Node();
            update(curr->l, s, m, v);
        }
    }
    int query(Node *curr, int s, int e, int x) {
        if(!curr) return -INF;
        int tmp=curr->v[0]*x+curr->v[1];
        if(s==e) return tmp;
        int m=(s+e)/2;
        if(x<=m) return max(tmp, query(curr->l, s, m, x));
        else return max(tmp, query(curr->r, m+1, e, x));
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++) {
        cin>>t[i]>>a[i]>>b[i]>>c[i], c[i]/=2;
        cx.push_back(t[i]+a[i]), cy.push_back(t[i]-a[i]);
        if(a[i]<b[i]) cx.push_back(t[i]+2*b[i]-a[i]);
        else cy.push_back(t[i]+a[i]-2*b[i]);
    }
    sort(cx.begin(), cx.end()), cx.erase(unique(cx.begin(), cx.end()), cx.end());
    sort(cy.begin(), cy.end()), cy.erase(unique(cy.begin(), cy.end()), cy.end());
    for(int i=1; i<=n; i++) {
        if(a[i]<b[i]) {
            int l=lower_bound(cx.begin(), cx.end(), t[i]+a[i])-cx.begin()+1;
            int r=lower_bound(cx.begin(), cx.end(), t[i]+2*b[i]-a[i])-cx.begin()+1;
            int p=lower_bound(cy.begin(), cy.end(), t[i]-a[i])-cy.begin()+1;
            for(int j=l+1; j<=r; j++) uv[j][p]=max(uv[j][p], c[i]);
        }
        else {
            int l=lower_bound(cy.begin(), cy.end(), t[i]-a[i])-cy.begin()+1;
            int r=lower_bound(cy.begin(), cy.end(), t[i]+a[i]-2*b[i])-cy.begin()+1;
            int p=lower_bound(cx.begin(), cx.end(), t[i]+a[i])-cx.begin()+1;
            for(int j=l+1; j<=r; j++) lv[p][j]=max(lv[p][j], c[i]);
        }
    }
    for(int i=cx.size(); i>=1; i--) for(int j=cy.size(); j>=1; j--) {
        if(i>1) dp[i-1][j]=max(dp[i-1][j], dp[i][j]+uv[i][j]*(cx[i-1]-cx[i-2]));
        if(j>1) dp[i][j-1]=max(dp[i][j-1], dp[i][j]+lv[i][j]*(cy[j-1]-cy[j-2]));
    }
    for(int i=1; i<=q; i++) {
        cin>>p[i]>>x[i];
        int i1=lower_bound(cx.begin(), cx.end(), p[i]+x[i])-cx.begin()+1;
        int i2=lower_bound(cy.begin(), cy.end(), p[i]-x[i])-cy.begin()+1;
        ans[i]=dp[i1][i2];
        vec1[i1].push_back({p[i]-x[i], i}), vec2[i2].push_back({p[i]+x[i], i});
    }
    for(int i=1; i<=cx.size(); i++) {
        sort(vec1[i].begin(), vec1[i].end());
        for(int j=vec1[i].size()-1, t=cy.size(); j>=0; j--) {
            while(cy[t-1]>=vec1[i][j].first) T.update(-uv[i][t], uv[i][t]*cx[i-1]+dp[i][t]), t--;
            ans[vec1[i][j].second]=max(ans[vec1[i][j].second], T.query(p[vec1[i][j].second]+x[vec1[i][j].second]));
        }
        T.clear();
    }
    for(int i=1; i<=cy.size(); i++) {
        sort(vec2[i].begin(), vec2[i].end());
        for(int j=vec2[i].size()-1, t=cx.size(); j>=0; j--) {
            while(cx[t-1]>=vec2[i][j].first) T.update(-lv[t][i], lv[t][i]*cy[i-1]+dp[t][i]), t--;
            ans[vec2[i][j].second]=max(ans[vec2[i][j].second], T.query(p[vec2[i][j].second]-x[vec2[i][j].second]));
        }
        T.clear();
    }
    for(int i=1; i<=q; i++) cout<<ans[i]<<"\n";
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52