Submission #847798

#	Time	Username	Problem	Language	Result	Execution time	Memory
847798		Urvuk3	Catfish Farm (IOI22_fish)	C++17	100 / 100	611 ms	162640 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

const int mxM=3e5+1;
const int mxN=1e5+1;
const int mxC=6e6;

int N,M;
ll seg[mxC],_l[mxC],_r[mxC],roots[mxC];
int idxx;

void Update(int node,int l,int r,int idx,ll val){
    if(l==r){
        seg[node]+=val;
        return;
    }
    if(idx<=mid){
        if(!_l[node]) _l[node]=++idxx;
        Update(_l[node],l,mid,idx,val);
    }
    else{
        if(!_r[node]) _r[node]=++idxx;
        Update(_r[node],mid+1,r,idx,val);
    }
    seg[node]=(_l[node] ? seg[_l[node]] : 0)+(_r[node] ? seg[_r[node]] : 0);
}

ll Query(int node,int l,int r,int L,int R){
    if(L>R) return 0;
    if(L<=l && r<=R) return seg[node];
    ll ret=0;
    if(L<=mid && _l[node]) ret+=Query(_l[node],l,mid,L,R);
    if(R>mid && _r[node]) ret+=Query(_r[node],mid+1,r,L,R);
    return ret;
}

ll Query(int col,int L,int R){
    return Query(roots[col],0,N-1,L,R);
}

vector<int> piers[mxN];
vector<pair<int,ll>> w[mxN];
vector<ll> dp[2][mxN];
vector<ll> mx(mxN);

void MaxSelf(ll& x,ll v){
    x=max(x,v);
}

long long max_weights(int N1,int M1,vector<int> X,vector<int> Y,vector<int> W){
    N=N1; M=M1;
    ll sum0=0,sum1=0;
    for(int i=0;i<M;i++){
        if(X[i]-1>=0) piers[X[i]-1].pb(Y[i]+1);
        if(X[i]+1<N) piers[X[i]+1].pb(Y[i]+1);
        w[X[i]].pb({Y[i],W[i]});
        if(X[i]==0) sum0+=W[i];
        else sum1+=W[i];
    }
    for(int i=0;i<N;i++){
        sort(all(piers[i]));
        piers[i].resize(distance(piers[i].begin(),unique(all(piers[i]))));
        sort(all(w[i]));
        roots[i]=++idxx;
        for(auto p:w[i]){
            Update(roots[i],0,N-1,p.fi,p.se);
        }
        dp[0][i].resize(sz(piers[i]));
        dp[1][i].resize(sz(piers[i]));
    }
    for(int i=0;i<N;i++){
        if(i){
            if(i>=3){
                for(int j=0;j<sz(piers[i]);j++){
                    int p=piers[i][j];
                    MaxSelf(dp[0][i][j],mx[i-3]+Query(i-1,0,p-1));
                }
            }
            if(i>=2){
                int j1=-1;
                ll pref=0;
                for(int j=0;j<sz(piers[i]);j++){
                    int p=piers[i][j];
                    while(j1+1<sz(piers[i-2]) && piers[i-2][j1+1]<=p){
                        MaxSelf(pref,max(dp[0][i-2][j1+1],dp[1][i-2][j1+1]));
                        j1++;
                    }
                    MaxSelf(dp[0][i][j],pref+Query(i-1,0,p-1));
                }
                j1=sz(piers[i-2]);
                pref=0;
                for(int j=sz(piers[i])-1;j>=0;j--){
                    int p=piers[i][j];
                    while(j1-1>=0 && piers[i-2][j1-1]>p){
                        MaxSelf(pref,max(dp[0][i-2][j1-1],dp[1][i-2][j1-1])+Query(i-1,0,piers[i-2][j1-1]-1));
                        j1--;
                    }
                    MaxSelf(dp[0][i][j],pref);
                }
            }
            for(int j=0;j<sz(piers[i]);j++){
                int p=piers[i][j];
                MaxSelf(dp[0][i][j],Query(i-1,0,p-1));
            }
            int j1=-1;
            ll pref=0;
            for(int j=0;j<sz(piers[i]);j++){
                int p=piers[i][j];
                while(j1+1<sz(piers[i-1]) && piers[i-1][j1+1]<=p){
                    MaxSelf(pref,dp[0][i-1][j1+1]+Query(i-1,piers[i-1][j1+1],N-1));
                    j1++;
                }
                MaxSelf(dp[0][i][j],pref-Query(i-1,p,N-1));
            }
            j1=sz(piers[i-1]);
            pref=0;
            for(int j=sz(piers[i])-1;j>=0;j--){
                int p=piers[i][j];
                while(j1-1>=0 && piers[i-1][j1-1]>p){
                    MaxSelf(pref,max(dp[0][i-1][j1-1],dp[1][i-1][j1-1])+Query(i,0,piers[i-1][j1-1]-1));
                    j1--;
                }
                MaxSelf(dp[1][i][j],pref-Query(i,0,p-1));
            }
        }
        if(i+1<N){
            for(int j=0;j<sz(piers[i]);j++){
                int p=piers[i][j];
                MaxSelf(mx[i],max(dp[0][i][j],dp[1][i][j])+Query(i+1,0,p-1));
            }
            if(i) MaxSelf(mx[i],mx[i-1]);
        }
    }
    ll res=mx[N-2];
    for(int j=0;j<sz(piers[N-1]);j++){
        res=max(res,max(dp[0][N-1][j],dp[1][N-1][j]));
    }
    return res;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16