Submission #1183390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183390		imarn	Catfish Farm (IOI22_fish)	C++17	12 / 100	246 ms	54156 KiB

fish

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<double>
using namespace std;
const int mxn=1e5+5;
vector<int>g[mxn];
vector<ll>sm[mxn];
vector<ll>qr[mxn];
vector<ll>lo[mxn],up[mxn];
long long max_weights(int N, int M,vi X,vi Y,vi W){
    for(int i=0;i<M;i++)g[X[i]+1].pb(Y[i]);
    for(int i=0;i<=N+1;i++)g[i].pb(-1),g[i].pb(N),sort(all(g[i])),g[i].erase(unique(all(g[i])),g[i].end()),sm[i].resize(g[i].size(),0);
    for(int i=0;i<M;i++)sm[X[i]+1][lb(g[X[i]+1],Y[i])]+=W[i];
    for(int i=0;i<=N+1;i++)for(int j=1;j<sm[i].size();j++)sm[i][j]+=sm[i][j-1];
    for(int i=0;i<M;i++)qr[X[i]].pb(Y[i]),qr[X[i]+2].pb(Y[i]);ll rs=0;
    for(int i=0;i<=N+1;i++)qr[i].pb(-1),qr[i].pb(N),sort(all(qr[i])),qr[i].erase(unique(all(qr[i])),qr[i].end()),lo[i].resize(qr[i].size()),up[i].resize(qr[i].size());
    for(int j=0;j<qr[1].size();j++){
        rs=max(rs,sm[2][ub(g[2],qr[1][j])-1]);
    }
    for(int i=2;i<=N;i++){
        int id=0;ll up_mx=0,lo_mx=0;
        for(int j=0;j<qr[i].size();j++){
            while(id<qr[i-1].size()&&qr[i-1][id]<=qr[i][j]){
                up_mx=max(up[i-1][id]-sm[i-1][ub(g[i-1],qr[i-1][id])-1],up_mx);id++;
                id++;
            }up[i][j]=max(up[i][j],up_mx+sm[i-1][ub(g[i-1],qr[i][j])-1]);
        }id=(int)qr[i-1].size()-1;up_mx=0,lo_mx=0;
        for(int j=(int)qr[i].size()-1;j>=0;j--){
            while(id>=0&&qr[i-1][id]>=qr[i][j]){
                up_mx=max(up[i-1][id]+sm[i][ub(g[i],qr[i-1][id])-1],up_mx);
                lo_mx=max(lo[i-1][id]+sm[i][ub(g[i],qr[i-1][id])-1],lo_mx);
                id--;
            }lo[i][j]=max(lo[i][j],max(up_mx,lo_mx)-sm[i][ub(g[i],qr[i][j])-1]);
        }ll mx=0;
        for(int j=0;j<qr[i-2].size();j++)mx=max({mx,lo[i-2][j],up[i-2][j]});
        for(int j=0;j<qr[i].size();j++)up[i][j]=max(up[i][j],mx+sm[i-1][ub(g[i-1],qr[i][j])-1]);
        for(int j=0;j<qr[i].size();j++){
            rs=max(rs,max(up[i][j],lo[i][j])+sm[i+1][ub(g[i+1],qr[i][j])-1]);
        }

    }
    return rs;
}

• 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