oj.uz

Submission #847546

# Submission time Handle Problem Language Result Execution time Memory
847546 2023-09-09T20:50:21 Z Urvuk3 Catfish Farm (IOI22_fish) C++17
12 / 100
 469 ms 172516 KB 
#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 seg[mxC],_l[mxC],_r[mxC],roots[mxC];
int idxx;

void Update(int node,int l,int r,int idx,ll val){
    if(l==r){
        seg[node]+=val;
        return;
    }
    if(idx<=mid){
        if(!_l[node]) _l[node]=++idxx;
        Update(_l[node],l,mid,idx,val);
    }
    else{
        if(!_r[node]) _r[node]=++idxx;
        Update(_r[node],mid+1,r,idx,val);
    }
    seg[node]=(_l[node] ? seg[_l[node]] : 0)+(_r[node] ? seg[_r[node]] : 0);
}

ll Query(int node,int l,int r,int L,int R){
    if(L>R) return 0;
    if(L<=l && r<=R) return seg[node];
    ll ret=0;
    if(L<=mid && _l[node]) ret+=Query(_l[node],l,mid,L,R);
    if(R>mid && _r[node]) ret+=Query(_r[node],mid+1,r,L,R);
    return ret;
}

ll Query(int col,int L,int R){
    return Query(roots[col],0,N-1,L,R);
}

vector<int> piers[mxN];
vector<pair<int,ll>> w[mxN];
vector<ll> dp[2][mxN];
vector<ll> mx(mxN);

void MaxSelf(ll& x,ll v){
    x=max(x,v);
}

long long max_weights(int N1,int M1,vector<int> X,vector<int> Y,vector<int> W){
    N=N1; M=M1;
    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++){
        sort(all(piers[i]));
        piers[i].resize(distance(piers[i].begin(),unique(all(piers[i]))));
        sort(all(w[i]));
        roots[i]=++idxx;
        if(w[i].empty()) Update(roots[i],0,N-1,0,0);
        for(auto p:w[i]){
            Update(roots[i],0,N-1,p.fi,p.se);
        }
        dp[0][i].resize(sz(piers[i]));
        dp[1][i].resize(sz(piers[i]));
    }
    for(int i=0;i<N;i++){
        if(i){
            if(i>=3){
                for(int j=0;j<sz(piers[i]);j++){
                    int p=piers[i][j];
                    MaxSelf(dp[0][i][j],mx[i-3]+Query(i-1,0,p-1));
                }
            }
            if(i>=2){
                int j1=-1;
                for(int j=0;j<sz(piers[i]);j++){
                    int p=piers[i][j];
                    while(j1+1<sz(piers[i-2]) && piers[i-2][j1+1]<=p){
                        MaxSelf(dp[0][i][j],max(dp[0][i-2][j1+1],dp[1][i-2][j1+1])+Query(i-1,0,p-1));
                        j1++;
                    }
                }
                j1=sz(piers[i-2]);
                for(int j=sz(piers[i])-1;j>=0;j--){
                    int p=piers[i][j];
                    while(j1-1>=0 && piers[i-2][j1-1]>p){
                        MaxSelf(dp[0][i][j],max(dp[0][i-2][j1-1],dp[1][i-2][j1-1])+Query(i-1,0,piers[i-2][j1-1]-1));
                        j1--;
                    }
                }
            }
            for(int j=0;j<sz(piers[i]);j++){
                int p=piers[i][j];
                MaxSelf(dp[0][i][j],Query(0,0,p-1));
            }
            int j1=-1;
            for(int j=0;j<sz(piers[i]);j++){
                int p=piers[i][j];
                while(j1+1<sz(piers[i-1]) && piers[i-1][j1+1]<=p){
                    MaxSelf(dp[0][i][j],dp[0][i-1][j1+1]+Query(i-1,piers[i-1][j1+1],p-1));
                    j1++;
                }
            }
            j1=sz(piers[i-1]);
            for(int j=sz(piers[i])-1;j>=0;j--){
                int p=piers[i][j];
                while(j1-1>=0 && piers[i-1][j1-1]>p){
                    MaxSelf(dp[1][i][j],max(dp[0][i-1][j1-1],dp[1][i-1][j1-1])+Query(i,p,piers[i-1][j1-1]-1));
                    j1--;
                }
            }
        }
        if(i+1<N){
            for(int j=0;j<sz(piers[i]);j++){
                int p=piers[i][j];
                MaxSelf(mx[i],max(dp[0][i][j],dp[1][i][j])+Query(i+1,0,p-1));
            }
            if(i) MaxSelf(mx[i],mx[i-1]);
        }
    }
    ll res=mx[N-2];
    for(int j=0;j<sz(piers[N-1]);j++){
        res=max(res,max(dp[0][N-1][j],dp[1][N-1][j]));
    }
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 47668 KB Output is correct
2 Correct 76 ms 52612 KB Output is correct
3 Correct 19 ms 42072 KB Output is correct
4 Correct 19 ms 42076 KB Output is correct
5 Correct 321 ms 83820 KB Output is correct
6 Correct 469 ms 172516 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Incorrect 152 ms 59316 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42276 KB Output is correct
2 Correct 20 ms 42072 KB Output is correct
3 Correct 76 ms 47872 KB Output is correct
4 Correct 59 ms 48468 KB Output is correct
5 Correct 130 ms 58640 KB Output is correct
6 Correct 117 ms 57916 KB Output is correct
7 Correct 121 ms 58368 KB Output is correct
8 Correct 121 ms 58700 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Correct 3 ms 13656 KB Output is correct
3 Correct 3 ms 13656 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 2 ms 13660 KB Output is correct
6 Correct 3 ms 13660 KB Output is correct
7 Correct 3 ms 13660 KB Output is correct
8 Correct 3 ms 13656 KB Output is correct
9 Correct 4 ms 13724 KB Output is correct
10 Incorrect 4 ms 13916 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '798645060367'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Correct 3 ms 13656 KB Output is correct
3 Correct 3 ms 13656 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 2 ms 13660 KB Output is correct
6 Correct 3 ms 13660 KB Output is correct
7 Correct 3 ms 13660 KB Output is correct
8 Correct 3 ms 13656 KB Output is correct
9 Correct 4 ms 13724 KB Output is correct
10 Incorrect 4 ms 13916 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '798645060367'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Correct 3 ms 13656 KB Output is correct
3 Correct 3 ms 13656 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 2 ms 13660 KB Output is correct
6 Correct 3 ms 13660 KB Output is correct
7 Correct 3 ms 13660 KB Output is correct
8 Correct 3 ms 13656 KB Output is correct
9 Correct 4 ms 13724 KB Output is correct
10 Incorrect 4 ms 13916 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '798645060367'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42276 KB Output is correct
2 Correct 20 ms 42072 KB Output is correct
3 Correct 76 ms 47872 KB Output is correct
4 Correct 59 ms 48468 KB Output is correct
5 Correct 130 ms 58640 KB Output is correct
6 Correct 117 ms 57916 KB Output is correct
7 Correct 121 ms 58368 KB Output is correct
8 Correct 121 ms 58700 KB Output is correct
9 Correct 167 ms 69764 KB Output is correct
10 Incorrect 103 ms 45108 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36359530063629'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 47668 KB Output is correct
2 Correct 76 ms 52612 KB Output is correct
3 Correct 19 ms 42072 KB Output is correct
4 Correct 19 ms 42076 KB Output is correct
5 Correct 321 ms 83820 KB Output is correct
6 Correct 469 ms 172516 KB Output is correct
7 Correct 3 ms 13656 KB Output is correct
8 Incorrect 152 ms 59316 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
9 Halted 0 ms 0 KB -