Submission #721341

#	Time	Username	Problem	Language	Result	Execution time	Memory
721341		bin9638	Catfish Farm (IOI22_fish)	C++17	100 / 100	816 ms	96716 KiB

fish

#include <bits/stdc++.h>

#ifndef SKY
#include "fish.h"
#endif // SKY

using namespace std;

#define N 100010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,ll>
#define pb push_back

struct IT
{
    vector<ll>ST;
    int num_node=0;

    void init(int n)
    {
        num_node=n;
        ST.resize(n*4+1,-1e18);
    }

    void update(int id,int l,int r,int i,ll val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]=max(ST[id],val);
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id]=max(ST[id*2],ST[id*2+1]);
    }

    void gan(int i,ll val)
    {
        update(1,1,num_node,i,val);
    }

    ll get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return -1e18;
        if(l>=u&&r<=v)
            return ST[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }

    ll solve(int u,int v)
    {
        return get(1,1,num_node,u,v);
    }
}T[N][4];

int n,m;
vector<ii>lis[N];
vector<ll>sum[N];
ll ans=0;

ll get_cost(int i,int heigh)
{
    if(lis[i].empty())
        return 0;
    if(heigh<lis[i][0].fs)
        return 0;
    //cout<<i<<" "<<heigh<<" "<<prev(upper_bound(lis[i].begin(),lis[i].end(),ii{heigh,1e18}))-lis[i].begin()<<endl;
    return sum[i][prev(upper_bound(lis[i].begin(),lis[i].end(),ii{heigh,1e18}))-lis[i].begin()];
}

ll max_weights(int nnn, int mmm, vector<int> X, vector<int> Y,vector<int> W)
{
    n=nnn;
    m=mmm;
    for(int i=0;i<m;i++)
    {
        lis[X[i]+1].pb({Y[i]+1,W[i]});
    }
    for(int i=1;i<=n;i++)
    {
        lis[i].pb({n+1,0});
        sort(lis[i].begin(),lis[i].end());
    }
    for(int i=1;i<=n;i++)
    {
        T[i][0].init(lis[i].size());
        T[i][1].init(lis[i].size());
        T[i][2].init(lis[i].size());
        T[i][3].init(lis[i].size());
        sum[i].resize(lis[i].size()+1,0);
        for(int j=0;j<lis[i].size();j++)
            sum[i][j]=(j>0 ? sum[i][j-1] : 0)+lis[i][j].sc;
    }
    for(int j=0;j<lis[1].size();j++)
    {
        T[1][0].gan(j+1,get_cost(2,lis[1][j].fs-1));
        T[1][1].gan(j+1,-get_cost(1,lis[1][j].fs-1));
       // if(j==0)cout<<lis[1][j].fs<<" "<<-get_cost(1,lis[1][j].fs-1)<<endl;
        T[1][2].gan(j+1,get_cost(2,lis[1][j].fs-1));
        T[1][3].gan(j+1,0);
    }
    //cout<<n<<" "<<m<<endl;
  // return 0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<lis[i].size();j++)
        {
           //  cout<<i<<" "<<j<<endl;
            if(lis[i][j].fs<=lis[i-1].back().fs)
            {
                int vt=lower_bound(lis[i-1].begin(),lis[i-1].end(),ii{lis[i][j].fs,0})-lis[i-1].begin()+1;
              //  cout<<vt<<endl;
                ll val=T[i-1][0].solve(vt,lis[i-1].size())-get_cost(i,lis[i][j].fs-1);
                ans=max(ans,val);
              //  cout<<val<<endl;
                T[i][0].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                T[i][2].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                T[i][3].gan(j+1,val);
            }
            if(lis[i][j].fs>=lis[i-1][0].fs)
            {
                int vt=(lis[i][j].fs>=lis[i-1].back().fs ? lis[i-1].size() :
                         prev(upper_bound(lis[i-1].begin(),lis[i-1].end(),ii{lis[i][j].fs,1e18}))-lis[i-1].begin()+1);
                ll val=T[i-1][1].solve(1,vt)+get_cost(i-1,lis[i][j].fs-1);
             //    cout<<val<<" "<<vt<<" "<<T[i-1][1].solve(1,vt)<<endl;
                ans=max(ans,val);
                T[i][0].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                T[i][1].gan(j+1,val-get_cost(i,lis[i][j].fs-1));
                T[i][2].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                T[i][3].gan(j+1,val);
            }
            if(i>2)
            {
                if(lis[i][j].fs<=lis[i-2].back().fs)
                {
                    int vt=lower_bound(lis[i-2].begin(),lis[i-2].end(),ii{lis[i][j].fs,0})-lis[i-2].begin()+1;
                    ll val=T[i-2][2].solve(vt,lis[i-2].size());//-get_cost(i,lis[i][j].fs-1);
                    ans=max(ans,val);
                    T[i][0].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                    T[i][1].gan(j+1,val-get_cost(i,lis[i][j].fs-1));
                    T[i][2].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                    T[i][3].gan(j+1,val);
                }
                if(lis[i][j].fs>=lis[i-2][0].fs)
                {
                    int vt=(lis[i][j].fs>=lis[i-2].back().fs ? lis[i-2].size() :
                            prev(upper_bound(lis[i-2].begin(),lis[i-2].end(),ii{lis[i][j].fs,1e18}))-lis[i-2].begin()+1);
                    ll val=T[i-2][1].solve(1,vt)+get_cost(i-1,lis[i][j].fs-1);
                    ans=max(ans,val);
                    T[i][0].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                    T[i][1].gan(j+1,val-get_cost(i,lis[i][j].fs-1));
                    T[i][2].gan(j+1,val+get_cost(i+1,lis[i][j].fs-1));
                    T[i][3].gan(j+1,val);
                }
            }
        }
    return ans;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<int>X(m),Y(m),W(m);
    for(int i=0;i<m;i++)
        cin>>X[i];//>>Y[i]>>W[i];
          for(int i=0;i<m;i++)
        cin>>Y[i];//>>Y[i]>>W[i];
          for(int i=0;i<m;i++)
        cin>>W[i];//>>Y[i]>>W[i];
    cout<<max_weights(n,m,X,Y,W);
    return 0;
}
#endif

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int j=0;j<lis[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
fish.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int j=0;j<lis[1].size();j++)
      |                 ~^~~~~~~~~~~~~~
fish.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int j=0;j<lis[i].size();j++)
      |                     ~^~~~~~~~~~~~~~

• 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