oj.uz

Submission #977256

# Submission time Handle Problem Language Result Execution time Memory
977256 2024-05-07T15:04:33 Z AlperenT_ Sequence (APIO23_sequence) C++17
50 / 100
 2000 ms 128080 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 = -inf ;
    mnp = mns = inf ;
    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] ;
 
int ch(int x){
  node nw ; 
  rep(i , 0 , 4*n){
    node x ;
    seg[i] = x;
  }
  rep(i ,1 ,n){
    upd(i , 1) ;
  }
  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])) ;
  }
  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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 103172 KB Output is correct
2 Correct 20 ms 103000 KB Output is correct
3 Correct 19 ms 103004 KB Output is correct
4 Correct 20 ms 103000 KB Output is correct
5 Correct 20 ms 103004 KB Output is correct
6 Correct 22 ms 103004 KB Output is correct
7 Correct 22 ms 103004 KB Output is correct
8 Correct 20 ms 103156 KB Output is correct
9 Correct 20 ms 103148 KB Output is correct
10 Correct 19 ms 103144 KB Output is correct
11 Correct 20 ms 103000 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 103172 KB Output is correct
2 Correct 20 ms 103000 KB Output is correct
3 Correct 19 ms 103004 KB Output is correct
4 Correct 20 ms 103000 KB Output is correct
5 Correct 20 ms 103004 KB Output is correct
6 Correct 22 ms 103004 KB Output is correct
7 Correct 22 ms 103004 KB Output is correct
8 Correct 20 ms 103156 KB Output is correct
9 Correct 20 ms 103148 KB Output is correct
10 Correct 19 ms 103144 KB Output is correct
11 Correct 20 ms 103000 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct
13 Correct 32 ms 103256 KB Output is correct
14 Correct 24 ms 103224 KB Output is correct
15 Correct 24 ms 103004 KB Output is correct
16 Correct 23 ms 102992 KB Output is correct
17 Correct 24 ms 103004 KB Output is correct
18 Correct 20 ms 103252 KB Output is correct
19 Correct 24 ms 103248 KB Output is correct
20 Correct 25 ms 103256 KB Output is correct
21 Correct 24 ms 103188 KB Output is correct
22 Correct 24 ms 103256 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 103172 KB Output is correct
2 Correct 308 ms 120828 KB Output is correct
3 Correct 506 ms 122452 KB Output is correct
4 Execution timed out 2048 ms 112212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 103000 KB Output is correct
2 Execution timed out 2032 ms 112900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 126652 KB Output is correct
2 Correct 346 ms 128080 KB Output is correct
3 Correct 208 ms 127568 KB Output is correct
4 Correct 204 ms 127316 KB Output is correct
5 Incorrect 371 ms 124244 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 103172 KB Output is correct
2 Correct 20 ms 103000 KB Output is correct
3 Correct 19 ms 103004 KB Output is correct
4 Correct 20 ms 103000 KB Output is correct
5 Correct 20 ms 103004 KB Output is correct
6 Correct 22 ms 103004 KB Output is correct
7 Correct 22 ms 103004 KB Output is correct
8 Correct 20 ms 103156 KB Output is correct
9 Correct 20 ms 103148 KB Output is correct
10 Correct 19 ms 103144 KB Output is correct
11 Correct 20 ms 103000 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct
13 Correct 32 ms 103256 KB Output is correct
14 Correct 24 ms 103224 KB Output is correct
15 Correct 24 ms 103004 KB Output is correct
16 Correct 23 ms 102992 KB Output is correct
17 Correct 24 ms 103004 KB Output is correct
18 Correct 20 ms 103252 KB Output is correct
19 Correct 24 ms 103248 KB Output is correct
20 Correct 25 ms 103256 KB Output is correct
21 Correct 24 ms 103188 KB Output is correct
22 Correct 24 ms 103256 KB Output is correct
23 Correct 100 ms 105740 KB Output is correct
24 Correct 93 ms 105808 KB Output is correct
25 Correct 97 ms 105884 KB Output is correct
26 Correct 233 ms 105012 KB Output is correct
27 Correct 211 ms 104532 KB Output is correct
28 Correct 258 ms 104532 KB Output is correct
29 Correct 373 ms 104428 KB Output is correct
30 Correct 336 ms 104464 KB Output is correct
31 Correct 353 ms 105060 KB Output is correct
32 Correct 29 ms 106580 KB Output is correct
33 Correct 243 ms 105696 KB Output is correct
34 Correct 311 ms 105708 KB Output is correct
35 Correct 255 ms 105564 KB Output is correct
36 Correct 433 ms 105812 KB Output is correct
37 Correct 395 ms 105672 KB Output is correct
38 Correct 421 ms 105772 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 103172 KB Output is correct
2 Correct 20 ms 103000 KB Output is correct
3 Correct 19 ms 103004 KB Output is correct
4 Correct 20 ms 103000 KB Output is correct
5 Correct 20 ms 103004 KB Output is correct
6 Correct 22 ms 103004 KB Output is correct
7 Correct 22 ms 103004 KB Output is correct
8 Correct 20 ms 103156 KB Output is correct
9 Correct 20 ms 103148 KB Output is correct
10 Correct 19 ms 103144 KB Output is correct
11 Correct 20 ms 103000 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct
13 Correct 32 ms 103256 KB Output is correct
14 Correct 24 ms 103224 KB Output is correct
15 Correct 24 ms 103004 KB Output is correct
16 Correct 23 ms 102992 KB Output is correct
17 Correct 24 ms 103004 KB Output is correct
18 Correct 20 ms 103252 KB Output is correct
19 Correct 24 ms 103248 KB Output is correct
20 Correct 25 ms 103256 KB Output is correct
21 Correct 24 ms 103188 KB Output is correct
22 Correct 24 ms 103256 KB Output is correct
23 Correct 308 ms 120828 KB Output is correct
24 Correct 506 ms 122452 KB Output is correct
25 Execution timed out 2048 ms 112212 KB Time limit exceeded
26 Halted 0 ms 0 KB -