Submission #831970

#	Time	Username	Problem	Language	Result	Execution time	Memory
831970		Urvuk3	Catfish Farm (IOI22_fish)	C++17	6 / 100	861 ms	622144 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 seg0[mxC],left0[mxC],right0[mxC],roots0[mxN];
ll idx0;

void Update0(int node,int l,int r,int idx,ll val){
    if(l==r){
        seg0[node]+=val;
        return;
    }
    if(idx<=mid){
        if(!left0[node]) left0[node]=++idx0;
        Update0(left0[node],l,mid,idx,val);
    }
    else{
        if(!right0[node]) right0[node]=++idx0;
        Update0(right0[node],mid+1,r,idx,val);
    }
    ll lnode=0; if(left0[node]) lnode=seg0[left0[node]];
    ll rnode=0; if(right0[node]) rnode=seg0[right0[node]];
    seg0[node]=lnode+rnode;
}

ll Query0(int node,int l,int r,int L,int R){
    if(L>R) return 0;
    if(L<=l && r<=R) return seg0[node];
    ll ret=0;
    if(L<=mid && left0[node]) ret+=Query0(left0[node],l,mid,L,R);
    if(R>mid && right0[node]) ret+=Query0(right0[node],mid+1,r,L,R);
    return ret;
}

struct Node{
    ll i,d;
};

Node Merge1(Node n1,Node n2){
    Node ret;
    ret.i=max(n1.i,n2.i);
    ret.d=max(n1.d,n2.d);
    return ret;
}

Node seg1[mxC];
ll left1[mxC],right1[mxC];
ll idx1;

void Update1(int col,int node,int l,int r,int pier,Node val){
    if(l==r){
        seg1[node].i=val.i;
        seg1[node].d=val.d;
        seg1[node].i+=Query0(roots0[col],0,N-1,pier,N-1);
        seg1[node].d+=Query0(roots0[col+1],0,N-1,0,pier-1);
        return;
    }
    if(pier<=mid){
        if(!left1[node]) left1[node]=++idx1;
        Update1(col,left1[node],l,mid,pier,val);
    }
    else{
        if(!right1[node]) right1[node]=++idx1;
        Update1(col,right1[node],mid+1,r,pier,val);
    }
    Node lnode=Node(); if(left1[node]) lnode=seg1[left1[node]];
    Node rnode=Node(); if(right1[node]) rnode=seg1[right1[node]];
    seg1[node]=Merge1(lnode,rnode);
}

Node Query1(int node,int l,int r,int L,int R){
    if(L>R) return Node();
    if(L<=l && r<=R) return seg1[node];
    Node ret=Node();
    if(L<=mid && left1[node]) ret=Merge1(ret,Query1(left1[node],l,mid,L,R));
    if(R>mid && right1[node]) ret=Merge1(ret,Query1(right1[node],mid+1,r,L,R));
    return ret;
}

vector<int> piers[mxN];
vector<pair<int,ll>> w[mxN];

long long max_weights(int N1,int M1,vector<int> X,vector<int> Y,vector<int> W){
    N=N1; M=M1; idx1=1;
    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]});
    }
    for(int i=0;i<N;i++){
        if(!count(all(piers[i]),0)) piers[i].pb(0);
    }
    for(int i=0;i<N;i++){
        roots0[i]=++idx0;
        for(auto p:w[i]){
            Update0(roots0[i],0,N-1,p.fi,p.se);
        }
    }
    ll res=0;
    int prev_root=-1,tmp_root=-1;
    for(int i=0;i<N;i++){
        if(i==0){
            for(int p:piers[i]){
                Update1(0,1,0,N,p,{0,0});
            }
            prev_root=1;
        }
        else{
            tmp_root=++idx1;
            for(int p:piers[i]){
                Node tmp=Node();
                Node n1=Query1(prev_root,0,N,0,p);
                tmp.i=max(n1.i,n1.d)-Query0(roots0[i-1],0,N-1,p,N-1);
                Node n2=Query1(prev_root,0,N,p+1,N);
                tmp.d=max(n2.i,n2.d)-Query0(roots0[i],0,N-1,0,p-1);
                if(i!=N-1) Update1(i,tmp_root,0,N,p,tmp);
                res=max({res,tmp.i,tmp.d});
            }
            prev_root=tmp_root;
        }
    }
    return res;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

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