oj.uz

Submission #1019074

# Submission time Handle Problem Language Result Execution time Memory
1019074 2024-07-10T12:55:23 Z bachhoangxuan Bodyguard (JOI21_bodyguard) C++17
100 / 100
 4278 ms 1255828 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int inf = 1e9;
const int maxn = 2805;
const int maxq = 3e6+5;

int N,Q;
int X[maxq],Y[maxq],U[maxn],V[maxn],W[maxn];
int ans[maxq];

int sx,sy;
vector<int> cx,cy;
vector<int> f[2*maxn][2*maxn];
int du[2*maxn][2*maxn],dr[2*maxn][2*maxn],dp[2*maxn][2*maxn];

struct line{
    int a,b,p=INF;
    line(int a=0,int b=0):a(a),b(b){}
    bool operator<(line o){return p<o.p;}
    bool operator<(int k){return p<k;}
};

vector<line> cht;

int fdiv(int a,int b){
    return a/b-((a^b)<0 && (a%b));
}

void isect(line &y,line l){
    if(y.a==l.a) y.p=(y.b>l.b?INF:-INF);
    else y.p=fdiv(y.b-l.b,l.a-y.a);
}

void add(int a,int b){
    line l=line(-a,b);
    while(!cht.empty() && cht.back().a>=l.a) cht.pop_back();
    if(!cht.empty()) isect(cht.back(),l);
    while((int)cht.size()>=2 && cht.end()[-2].p>=cht.back().p){
        cht.pop_back();
        isect(cht.back(),l);
    }
    cht.push_back(l);
}
int query(int x){
    x=-x;
    auto it=lower_bound(cht.begin(),cht.end(),x);
    return x*it->a+it->b;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> Q;
    cx.push_back(-inf);
    cy.push_back(-inf);
    for(int i=1;i<=N;i++){
        int t,a,b;cin >> t >> a >> b >> W[i];W[i]/=2;
        X[i]=t-a,Y[i]=t+a,U[i]=t+abs(a-b)-b,V[i]=t+abs(a-b)+b;
        cx.push_back(X[i]);cx.push_back(U[i]);
        cy.push_back(Y[i]);cy.push_back(V[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());
    sx=(int)cx.size();sy=(int)cy.size();
    cx.push_back(3*inf);cy.push_back(3*inf);

    for(int i=1;i<=N;i++){
        X[i]=lower_bound(cx.begin(),cx.end(),X[i])-cx.begin();
        Y[i]=lower_bound(cy.begin(),cy.end(),Y[i])-cy.begin();
        U[i]=lower_bound(cx.begin(),cx.end(),U[i])-cx.begin();
        V[i]=lower_bound(cy.begin(),cy.end(),V[i])-cy.begin();
        if(X[i]==U[i]) for(int j=Y[i];j<V[i];j++) du[X[i]][j]=max(du[X[i]][j],W[i]);
        else for(int j=X[i];j<U[i];j++) dr[j][Y[i]]=max(dr[j][Y[i]],W[i]);
    }
    for(int i=sx-1;i>=0;i--) for(int j=sy-1;j>=0;j--){
        dp[i][j]=max(dp[i+1][j]+dr[i][j]*(cx[i+1]-cx[i]),dp[i][j+1]+du[i][j]*(cy[j+1]-cy[j]));
        //cout << i << ' ' << j << ' ' << du[i][j] << ' ' << dr[i][j] << ' ' << dp[i][j] << '\n';
    }
    for(int i=1;i<=Q;i++){
        int x,y;cin >> x >> y;
        X[i]=x-y,Y[i]=x+y;
        x=lower_bound(cx.begin(),cx.end(),X[i])-cx.begin();
        y=lower_bound(cy.begin(),cy.end(),Y[i])-cy.begin();
        f[x][y].push_back(i);
    }
    for(int i=1;i<=sx;i++){
        cht.clear();
        for(int j=sy;j>=1;j--){
            add(dr[i-1][j],dp[i][j]);
            for(int id:f[i][j]) ans[id]=max(ans[id],query(cx[i]-X[id]));
        }
    }
    for(int j=1;j<=sy;j++){
        cht.clear();
        for(int i=sx;i>=1;i--){
            add(du[i][j-1],dp[i][j]);
            for(int id:f[i][j]) ans[id]=max(ans[id],query(cy[j]-Y[id]));
        }
    }
    for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3347 ms 1099420 KB Output is correct
2 Correct 3331 ms 1100692 KB Output is correct
3 Correct 1678 ms 958748 KB Output is correct
4 Correct 1186 ms 929792 KB Output is correct
5 Correct 1454 ms 1130520 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 1041492 KB Output is correct
2 Correct 998 ms 1040688 KB Output is correct
3 Correct 984 ms 1038640 KB Output is correct
4 Correct 305 ms 774220 KB Output is correct
5 Correct 909 ms 979240 KB Output is correct
6 Correct 884 ms 948496 KB Output is correct
7 Correct 862 ms 978772 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 1041492 KB Output is correct
2 Correct 998 ms 1040688 KB Output is correct
3 Correct 984 ms 1038640 KB Output is correct
4 Correct 305 ms 774220 KB Output is correct
5 Correct 909 ms 979240 KB Output is correct
6 Correct 884 ms 948496 KB Output is correct
7 Correct 862 ms 978772 KB Output is correct
8 Correct 958 ms 1041636 KB Output is correct
9 Correct 926 ms 1040144 KB Output is correct
10 Correct 952 ms 1036624 KB Output is correct
11 Correct 283 ms 774192 KB Output is correct
12 Correct 909 ms 979404 KB Output is correct
13 Correct 865 ms 948584 KB Output is correct
14 Correct 957 ms 979212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 1041492 KB Output is correct
2 Correct 998 ms 1040688 KB Output is correct
3 Correct 984 ms 1038640 KB Output is correct
4 Correct 305 ms 774220 KB Output is correct
5 Correct 909 ms 979240 KB Output is correct
6 Correct 884 ms 948496 KB Output is correct
7 Correct 862 ms 978772 KB Output is correct
8 Correct 958 ms 1041636 KB Output is correct
9 Correct 926 ms 1040144 KB Output is correct
10 Correct 952 ms 1036624 KB Output is correct
11 Correct 283 ms 774192 KB Output is correct
12 Correct 909 ms 979404 KB Output is correct
13 Correct 865 ms 948584 KB Output is correct
14 Correct 957 ms 979212 KB Output is correct
15 Correct 1014 ms 1045764 KB Output is correct
16 Correct 1042 ms 1045576 KB Output is correct
17 Correct 1063 ms 1040272 KB Output is correct
18 Correct 322 ms 776532 KB Output is correct
19 Correct 992 ms 981516 KB Output is correct
20 Correct 969 ms 951068 KB Output is correct
21 Correct 1010 ms 981484 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3347 ms 1099420 KB Output is correct
2 Correct 3331 ms 1100692 KB Output is correct
3 Correct 1678 ms 958748 KB Output is correct
4 Correct 1186 ms 929792 KB Output is correct
5 Correct 1454 ms 1130520 KB Output is correct
6 Correct 978 ms 1041492 KB Output is correct
7 Correct 998 ms 1040688 KB Output is correct
8 Correct 984 ms 1038640 KB Output is correct
9 Correct 305 ms 774220 KB Output is correct
10 Correct 909 ms 979240 KB Output is correct
11 Correct 884 ms 948496 KB Output is correct
12 Correct 862 ms 978772 KB Output is correct
13 Correct 958 ms 1041636 KB Output is correct
14 Correct 926 ms 1040144 KB Output is correct
15 Correct 952 ms 1036624 KB Output is correct
16 Correct 283 ms 774192 KB Output is correct
17 Correct 909 ms 979404 KB Output is correct
18 Correct 865 ms 948584 KB Output is correct
19 Correct 957 ms 979212 KB Output is correct
20 Correct 1014 ms 1045764 KB Output is correct
21 Correct 1042 ms 1045576 KB Output is correct
22 Correct 1063 ms 1040272 KB Output is correct
23 Correct 322 ms 776532 KB Output is correct
24 Correct 992 ms 981516 KB Output is correct
25 Correct 969 ms 951068 KB Output is correct
26 Correct 1010 ms 981484 KB Output is correct
27 Correct 4258 ms 1239208 KB Output is correct
28 Correct 4278 ms 1255828 KB Output is correct
29 Correct 2579 ms 1231608 KB Output is correct
30 Correct 1096 ms 946936 KB Output is correct
31 Correct 1802 ms 1099912 KB Output is correct
32 Correct 2643 ms 1141984 KB Output is correct
33 Correct 1622 ms 1143408 KB Output is correct