Submission #1056297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056297		boyliguanhan	Catfish Farm (IOI22_fish)	C++17	100 / 100	998 ms	157380 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int>fishies[100010];
map<int,ll>fishiess[100010];
unordered_map<int,ll>dp[100010][2];
int N;
inline ll ones(int col,int len){
    return (--fishiess[col].upper_bound(len))->second;
}
struct segtree{
    ll T[1<<18];
    ll query(int i,int l,int r,int ll,int rr){
        if(l>rr||ll>r) return -1e18;
        if(ll<=l&&r<=rr) return T[i];
        return max(query(i*2,l,l+r>>1,ll,rr),
                query(i*2+1,l+r+2>>1,r,ll,rr));
    }
    void upd(int i,int l,int r,int p,ll x){
        if(l==r)return void(T[i]=x);
        if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
        else upd(i*2+1,l+r+2>>1,r,p,x);
        T[i]=max(T[i*2],T[i*2+1]);
    }
};
struct a_data_type{
    segtree Sec,First,Overal,Third;
    inline ll sec(int pos){
        return Sec.query(1,0,N,pos,N);
    }
    inline ll first(int pos){
        return First.query(1,0,N,0,pos);
    }
    inline ll overal(int pos){
        return Overal.query(1,0,N,pos,N);
    }
    inline ll third(int pos){
        return Third.query(1,0,N,0,pos);
    }
    set<int>prv;
    void init(int i) {
        for(auto j:prv)
            Overal.upd(1,0,N,j,0),
            First.upd(1,0,N,j,0),
            Sec.upd(1,0,N,j,0),
            Third.upd(1,0,N,j,0);
        prv.clear();
        for(auto j:fishies[i]){
            prv.insert(--j);
            ll A=dp[i][0][j];
            ll B=dp[i][1][j];
            Overal.upd(1,0,N,j,max(A,B));
            First.upd(1,0,N,j,max(A,B)-ones(i+1,j));
            Sec.upd(1,0,N,j,A);
            Third.upd(1,0,N,j,B-ones(i,j)-ones(i+1,j));
        }
    }
} likehell[2];
ll max_weights(int N_,int M,vector<int> X,vector<int> Y,vector<int> W) {
    N=N_;
    for(int i=0;i<M;i++)
        fishies[X[i]+1].insert(Y[i]+1),
        fishiess[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++){
        fishiess[i][N+1];
        fishiess[i][0];
        auto it=++fishiess[i].begin();
        while(it!=fishiess[i].end())
            it->second+=prev(it)->second,it++;
    }
    for(int i=1;i<=N;i++)
        fishies[i].insert(1),
        fishies[i].insert(N+1);
    fishiess[N+1][0];
    for(auto i:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    int b=0;
    likehell[b].init(1);
    for(int i=2;i<=N;i++){
        for(auto rw:fishies[i]) {
            ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
            ll F=likehell[!b].first(rw-1);
            ll S=likehell[!b].overal(rw)-ones(i-1,rw-1);
            dp[i][1][rw-1]=cons+max(F,S);
        }
        for(auto rw2:fishies[i]){
            ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
            ll F=likehell[b].third(rw2-1);
            ll S=likehell[b].overal(rw2);
            dp[i][1][rw2-1]=max(dp[i][1][rw2-1],F+cons);
            dp[i][0][rw2-1]=S-ones(i,rw2-1)-ones(i-1,rw2-1)+cons;
        }
        for(auto rw2:fishies[i]) {
            ll K=likehell[b].sec(rw2-1)-ones(i,rw2-1);
            dp[i][0][rw2-1]=max(dp[i][0][rw2-1],ones(i+1,rw2-1)+K);
        }
        b=!b;
        likehell[b].init(i);
    }
    return likehell[b].overal(0);
}

Compilation message (stderr)

fish.cpp: In member function 'll segtree::query(int, int, int, int, int)':
fish.cpp:17:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         return max(query(i*2,l,l+r>>1,ll,rr),
      |                                ~^~
fish.cpp:18:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |                 query(i*2+1,l+r+2>>1,r,ll,rr));
      |                             ~~~^~
fish.cpp: In member function 'void segtree::upd(int, int, int, int, ll)':
fish.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
      |            ~^~
fish.cpp:22:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
      |                                ~^~
fish.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         else upd(i*2+1,l+r+2>>1,r,p,x);
      |                        ~~~^~

• 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