Submission #637738

#	Time	Username	Problem	Language	Result	Execution time	Memory
637738		pigeonbat	Catfish Farm (IOI22_fish)	C++17	12 / 100	544 ms	99584 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct pi{
    int x,y; ll w;
};
struct pi2{
    int y; ll up,down;
};

struct seg{
    ll tree[1<<18];
    int sz=1<<17;
    void up(ll v,int tg){
        tg|=sz;
        for(tree[tg]=max(tree[tg],v);tg>>=1;)
            tree[tg]=max(tree[tg<<1],tree[tg<<1|1]);
    }
    void init(ll v,int tg){
        for(tree[tg|=sz]=v;tg>>=1;)
            tree[tg]=max(tree[tg<<1],tree[tg<<1|1]);
    }
    ll qu(int l,int r){
        ll re=0;
        for(l|=sz,r|=sz;l<=r;l=(l+1)>>1,r=(r-1)>>1){
            if(l&1) re=max(re,tree[l++]);
            if(~r&1) re=max(re,tree[r--]);
        }
        return re;
    }
};

seg t1,t2;
vector<pii> v;
vector<pi> megi;
ll dp[100010],inf=1e18;;
map<int,ll> mp[1000010];

bool comp(pi &a,pi &b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    for(int i=0;i<N;i++) v.push_back({i,0});
    for(int i=0;i<M;i++){
        if(X[i]>0) v.push_back({X[i]-1,Y[i]+1});
        if(X[i]<N-1) v.push_back({X[i]+1,Y[i]+1});
    }
    for(int i=0;i<M;i++) megi.push_back({X[i],Y[i],W[i]});
    sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
    sort(megi.begin(),megi.end(),comp);
    int l1=0,l2=0,m=0;
    for(int i=0;i<(1<<18);i++) t1.tree[i]=t2.tree[i]=-inf;
    for(int i=0;i<N;i++){
        ll cnt=0;
        mp[i][-1]=0;
        while(m<M&&megi[m].x==i){
            cnt+=megi[m].w;
            mp[i][megi[m].y]=cnt;
            //printf("%d %d %lld\n",i,megi[m].y,cnt);
            m++;
        }
    }
    while(l2<(int)v.size()&&v[l2].first==0) l2++;
    for(int i=1;i<N;i++){
        vector<pi2> tmp;
        while(l2<(int)v.size()&&v[l2].first==i){
            auto it = mp[i-1].upper_bound(v[l2].second-1); it--;
            ll up=t1.qu(0, v[l2].second)+it->second;
            if(i==1) up=max(up,it->second);
            else up=max(up,dp[i-2]+it->second);
            it = mp[i].upper_bound(v[l2].second-1); it--;
            ll down=t2.qu(v[l2].second, N)-it->second;
            tmp.push_back({v[l2].second,up,down});
            dp[i]=max(dp[i],max(up,down));
            //printf("%d %d %lld %lld %lld\n",i,v[l2].second,up,down,it->second);
            l2++;
        }
        if(i==N-1) break;
        while(l1<(int)v.size()&&v[l1].first==i-1){
            t1.init(-inf, v[l1].second);
            t2.init(-inf, v[l1].second);
            l1++;
        }
        for(auto x:tmp){
            auto it = mp[i].upper_bound(x.y-1); it--;
            t1.up(x.up-it->second, x.y);
            it = mp[i+1].upper_bound(x.y-1); it--;
            t2.up(max(x.up,x.down)+it->second, x.y);
        }
    }
    return dp[N-1];
}

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