oj.uz

Submission #978317

# Submission time Handle Problem Language Result Execution time Memory
978317 2024-05-09T06:15:11 Z AlperenT_ Sequence (APIO23_sequence) C++17
0 / 100
 336 ms 206676 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 1e6 +10  , N = 1e5 +1  , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =1e9+7 ;
int a[maxn] , n;
 
struct node{
  int mxp , mnp , mxs , mns , sm ;
  node(){
    mxp = mxs = 0 ;
    mnp = mns = 0 ;
    sm =0 ;
  }
};
node seg[4*maxn] ;
node mrg(node a , node b){
  node r ;
  r.mxp = max(a.mxp , b.mxp + a.sm) ;
  r.mnp = min(a.mnp , b.mnp + a.sm) ;
  r.mxs = max(b.mxs , a.mxs + b.sm);
  r.mns = min(b.mns , a.mns + b.sm) ;
  r.sm = a.sm + b.sm ;
  return r ;
}
void upd(int x , int w, int p = 1, int l = 1 , int r = n){
  if(l == r){
    seg[p].mxp = seg[p].mxs = max(0 , w);
    seg[p].mnp = seg[p].mns = min(0 , w) ;
    seg[p].sm = w ;
    return ;
  }
  int pl = p<<1,pr=p<<1|1 , mid = (l+r)/2 ;
  if(mid>= x){
    upd(x,w,pl,l,mid);
  }else{
    upd(x,w,pr,mid+1,r);
  }
  seg[p] = mrg(seg[pl] , seg[pr]) ;
}
node z ; 
void query(int le ,int ri ,int p = 1, int l = 1, int r= n){
  int pl = p<<1,pr=p<<1|1 , mid = (l+r)/2 ;
  if(le > ri){
    z.mxp = z.mxs = z.mns = z.mnp = 0 ;z.sm =0 ;
    return ; 
  }
  if(le <= l && r <= ri){
    z = mrg(z , seg[p]) ;
    return;
  }
  if(mid >= ri){
    query(le,ri,pl,l,mid);
    return ;
  }
  if(mid < le){
    query(le,ri,pr,mid+1,r);
    return ;
  }
  query(le,ri,pl,l,mid) ;query(le,ri,pr,mid+1,r);
}
vector <int> vec[maxn] ;
 
void bui(int p = 1, int l = 1, int r= n){
    int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
    if(l == r){
        seg[p].sm = seg[p].mxp = seg[p].mxs = 1 ;
        seg[p].mnp = seg[p].mns = 0 ;
        return ;
    }
    bui(pl,l,mid);
    bui(pr,mid+1,r);
    seg[p] = mrg(seg[pl] , seg[pr]);
}
    node nw ;

int ch(int x){
    bui();
  rep(i ,1 ,n){
    if(sz(vec[i]) < x){
      for(int j : vec[i]){
        upd(j , -1) ; 
      }
      continue ;
    }
    rep(j , 0 ,x-1){
      upd(vec[i][j] , 0) ;
    }
    rep(j , 0 ,sz(vec[i])-x){
      int l = vec[i][j] , r = vec[i][j+x-1] ;
      z=nw;query(1 , l);node a1 = z;
      z=nw;query(r , n);node a2 = z ;
      z=nw;query(l,r);int sum = z.sm ; 
      if((sum >= 0 && sum+a1.mns+a2.mnp <= x) || (sum <= 0 && -(sum + a1.mxs + a2.mxp) <= x))return 1 ;
      upd(vec[i][j] , -1) ;
      if(i!=sz(vec[i])-x){
        upd(vec[i][j+x] , 0) ;
      }
    }
    per(j , sz(vec[i])-1 , 0){
      upd(vec[i][j] , -1) ;
    }
  }
  return 0 ;
}
 
int sequence(int N, vector<int> A) {
  n = N  ;
  rep(i , 1,n){
    a[i] = A[i-1] ;
    vec[a[i]].pb(i) ;
  }
  int mx = 0 ;
  rep(i , 1 , n){
    mx= max(mx ,sz(vec[i])) ;
  }
  if(mx > 2){
    cout << 1/0 ; 
  }
  int l = 1 , r= mx+1 ;
  while(r-l > 1){
    int mid = (l+r)/2 ;
    if(ch(mid) == 1) l = mid ;
    else r = mid ;
  }
  return l;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:128:14: warning: division by zero [-Wdiv-by-zero]
  128 |     cout << 1/0 ;
      |             ~^~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 206676 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 206676 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 206676 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 206676 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 126956 KB Output is correct
2 Correct 268 ms 126800 KB Output is correct
3 Correct 186 ms 126484 KB Output is correct
4 Correct 169 ms 126288 KB Output is correct
5 Incorrect 324 ms 123012 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 206676 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 206676 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -