oj.uz

Submission #831970

# Submission time Handle Problem Language Result Execution time Memory
831970 2023-08-20T18:53:04 Z Urvuk3 Catfish Farm (IOI22_fish) C++17
6 / 100
 861 ms 622144 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 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.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 60772 KB Output is correct
2 Correct 148 ms 68152 KB Output is correct
3 Correct 52 ms 51156 KB Output is correct
4 Correct 52 ms 51148 KB Output is correct
5 Correct 574 ms 126604 KB Output is correct
6 Runtime error 861 ms 622144 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 408 ms 80988 KB Output is correct
3 Correct 530 ms 92012 KB Output is correct
4 Correct 127 ms 60832 KB Output is correct
5 Correct 171 ms 68244 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 54 ms 51140 KB Output is correct
11 Correct 53 ms 51232 KB Output is correct
12 Correct 170 ms 66744 KB Output is correct
13 Correct 221 ms 75044 KB Output is correct
14 Correct 143 ms 63680 KB Output is correct
15 Correct 255 ms 70308 KB Output is correct
16 Correct 153 ms 63888 KB Output is correct
17 Correct 165 ms 70232 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 51204 KB Output is correct
2 Correct 54 ms 51220 KB Output is correct
3 Incorrect 153 ms 76460 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '8306231112681'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5012 KB Output is correct
9 Incorrect 3 ms 5140 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '67701654666'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5012 KB Output is correct
9 Incorrect 3 ms 5140 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '67701654666'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5012 KB Output is correct
9 Incorrect 3 ms 5140 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '67701654666'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 51204 KB Output is correct
2 Correct 54 ms 51220 KB Output is correct
3 Incorrect 153 ms 76460 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '8306231112681'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 60772 KB Output is correct
2 Correct 148 ms 68152 KB Output is correct
3 Correct 52 ms 51156 KB Output is correct
4 Correct 52 ms 51148 KB Output is correct
5 Correct 574 ms 126604 KB Output is correct
6 Runtime error 861 ms 622144 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -