oj.uz

Submission #889245

# Submission time Handle Problem Language Result Execution time Memory
889245 2023-12-19T08:42:15 Z kim Catfish Farm (IOI22_fish) C++17
9 / 100
 721 ms 167892 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=ll;
using pii=pair<ll,ll>;
#define f first
#define s second
#define eb emplace_back

i64 N,M;
i64 X[300005],Y[300005],W[300005];

vector<pii> pos;
vector<pair<i64,ll>> QS[300005];
vector<ll> dp[2];
i64 L[300005],R[300005];

ll qs(i64 x,i64 y){
  auto itr=upper_bound(QS[x].begin(),QS[x].end(),pair<i64,ll>(y,LLONG_MAX));
  --itr;
  return itr->s;
}
pii getRange(i64 x,i64 y1,i64 y2){
  return pii(lower_bound(pos.begin()+L[x],pos.begin()+R[x]+1,pii(x,y1))-pos.begin(),
             upper_bound(pos.begin()+L[x],pos.begin()+R[x]+1,pii(x,y2))-pos.begin()-1);
}
struct segment{
  vector<segment> child;
  i64 l,r,mid;
  ll mx[3];
  segment(i64 l_=0,i64 r_=0):l(l_),r(r_),mid(l+(r-l>>1)){
    mx[0]=mx[1]=mx[2]=0;
  }
  void build(){
    if(l==r) return;
    child.eb(l,mid),child.eb(mid+1,r);
    child[0].build(),child[1].build();
  }
  void upd(i64 i,i64 z,ll x){
    if(l==r) return void(mx[z]=x);
    if(i<=mid) child[0].upd(i,z,x);
    else child[1].upd(i,z,x);
    mx[z]=max(child[0].mx[z],child[1].mx[z]);
  }
  ll qr(i64 z,i64 l0,i64 r0){
    if(l0<=l&&r<=r0) return mx[z];
    if(l>r0||r<l0) return 0;
    return max(child[0].qr(z,l0,r0),child[1].qr(z,l0,r0));
  }
}t;

long long max_weights(int N_, int M_, std::vector<int> X_, std::vector<int> Y_,
                      std::vector<int> W_) {
  N=N_,M=M_;
  for(i64 i=1;i<=M;++i) X[i]=X_[i-1]+1,Y[i]=Y_[i-1]+1,W[i]=W_[i-1];

  for(i64 i=1;i<=M;++i){
    QS[X[i]].eb(Y[i],W[i]);
    if(X[i]>1) pos.eb(X[i]-1,Y[i]);
    if(X[i]<N) pos.eb(X[i]+1,Y[i]);
  }
  for(i64 i=1;i<=N;++i){
    QS[i].eb(0,0);
    sort(QS[i].begin(),QS[i].end());
    for(i64 j=1;j<QS[i].size();++j) QS[i][j].s+=QS[i][j-1].s;
    pos.eb(i,0);
  }
  pos.eb(0,0);
  pos.eb(N+1,0);
  QS[0].eb(0,0);
  QS[N+1].eb(0,0);
  sort(pos.begin(),pos.end());
  pos.erase(unique(pos.begin(),pos.end()),pos.end());
  for(i64 i=0;i<pos.size();++i){
    if(!L[pos[i].f]) L[pos[i].f]=i;
    R[pos[i].f]=i;
  }
  t=segment(0,pos.size()-1);
  t.build();
  dp[0]=dp[1]=vector<ll>(pos.size());

  i64 l,r;
  for(i64 i=1;i<pos.size();++i){
    auto &[x,y]=pos[i];
    tie(l,r)=getRange(x-1,0,y-1);
    if(l<=r) dp[0][i]=t.qr(1,l,r)+qs(x-1,y);
    if(i>3){
      tie(l,r)=getRange(x-2,0,y-1);
      if(l<=r) dp[0][i]=max(dp[0][i],t.qr(0,l,r)+qs(x-1,y));
    }

    tie(l,r)=getRange(x-1,y,N);
    if(l<=r) dp[1][i]=t.qr(2,l,r);
    if(i>2){
      tie(l,r)=getRange(x-2,y,N);
      if(l<=r) dp[1][i]=max(dp[1][i],t.qr(2,l,r));
    }
    if(i+1<pos.size()){
      t.upd(i,0,max(dp[0][i],dp[1][i]));
      t.upd(i,1,dp[0][i]-qs(x,y));
      t.upd(i,2,max(dp[0][i],dp[1][i])+qs(x+1,y));
    }
  }

  return dp[1].back();

//   /*
//   0,1: qrz_1: dp[i][k][z]
//   2:   qr0_2: dp[i][k][0]-qs[i][k]
//   3,4: qrz_3: dp[i][k][z]+qs[i+1][k]
//   */

}

Compilation message

fish.cpp: In constructor 'segment::segment(i64, i64)':
fish.cpp:32:50: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   32 |   segment(i64 l_=0,i64 r_=0):l(l_),r(r_),mid(l+(r-l>>1)){
      |                                                 ~^~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:66:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(i64 j=1;j<QS[i].size();++j) QS[i][j].s+=QS[i][j-1].s;
      |                 ~^~~~~~~~~~~~~
fish.cpp:75:16: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(i64 i=0;i<pos.size();++i){
      |               ~^~~~~~~~~~~
fish.cpp:84:16: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(i64 i=1;i<pos.size();++i){
      |               ~^~~~~~~~~~~
fish.cpp:99:11: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     if(i+1<pos.size()){
      |        ~~~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 55704 KB Output is correct
2 Correct 164 ms 62364 KB Output is correct
3 Correct 63 ms 37664 KB Output is correct
4 Correct 64 ms 37580 KB Output is correct
5 Correct 721 ms 166056 KB Output is correct
6 Correct 711 ms 167892 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 389 ms 91272 KB Output is correct
3 Correct 475 ms 105652 KB Output is correct
4 Correct 146 ms 56240 KB Output is correct
5 Correct 168 ms 62244 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12724 KB Output is correct
10 Correct 64 ms 37576 KB Output is correct
11 Correct 65 ms 37576 KB Output is correct
12 Correct 226 ms 71092 KB Output is correct
13 Correct 266 ms 82360 KB Output is correct
14 Correct 204 ms 63492 KB Output is correct
15 Correct 246 ms 68712 KB Output is correct
16 Correct 199 ms 64188 KB Output is correct
17 Correct 221 ms 68924 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 37576 KB Output is correct
2 Correct 71 ms 37664 KB Output is correct
3 Incorrect 136 ms 52112 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 37576 KB Output is correct
2 Correct 71 ms 37664 KB Output is correct
3 Incorrect 136 ms 52112 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 55704 KB Output is correct
2 Correct 164 ms 62364 KB Output is correct
3 Correct 63 ms 37664 KB Output is correct
4 Correct 64 ms 37580 KB Output is correct
5 Correct 721 ms 166056 KB Output is correct
6 Correct 711 ms 167892 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 389 ms 91272 KB Output is correct
9 Correct 475 ms 105652 KB Output is correct
10 Correct 146 ms 56240 KB Output is correct
11 Correct 168 ms 62244 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12724 KB Output is correct
16 Correct 64 ms 37576 KB Output is correct
17 Correct 65 ms 37576 KB Output is correct
18 Correct 226 ms 71092 KB Output is correct
19 Correct 266 ms 82360 KB Output is correct
20 Correct 204 ms 63492 KB Output is correct
21 Correct 246 ms 68712 KB Output is correct
22 Correct 199 ms 64188 KB Output is correct
23 Correct 221 ms 68924 KB Output is correct
24 Correct 70 ms 37576 KB Output is correct
25 Correct 71 ms 37664 KB Output is correct
26 Incorrect 136 ms 52112 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
27 Halted 0 ms 0 KB -