oj.uz

Submission #979879

# Submission time Handle Problem Language Result Execution time Memory
979879 2024-05-11T14:33:05 Z AlperenT_ Sequence (APIO23_sequence) C++17
70 / 100
 2000 ms 75640 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 = 5e5 +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(j!=sz(vec[i])-x){
        upd(vec[i][j+x] , 0) ;
      }
    }
    per(j , sz(vec[i])-1 , sz(vec[i])-x){
      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 24 ms 51796 KB Output is correct
2 Correct 13 ms 52056 KB Output is correct
3 Correct 10 ms 51908 KB Output is correct
4 Correct 10 ms 51804 KB Output is correct
5 Correct 12 ms 51884 KB Output is correct
6 Correct 11 ms 51804 KB Output is correct
7 Correct 10 ms 51688 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 12 ms 51804 KB Output is correct
10 Correct 10 ms 51916 KB Output is correct
11 Correct 11 ms 51804 KB Output is correct
12 Correct 10 ms 51804 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51796 KB Output is correct
2 Correct 13 ms 52056 KB Output is correct
3 Correct 10 ms 51908 KB Output is correct
4 Correct 10 ms 51804 KB Output is correct
5 Correct 12 ms 51884 KB Output is correct
6 Correct 11 ms 51804 KB Output is correct
7 Correct 10 ms 51688 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 12 ms 51804 KB Output is correct
10 Correct 10 ms 51916 KB Output is correct
11 Correct 11 ms 51804 KB Output is correct
12 Correct 10 ms 51804 KB Output is correct
13 Correct 11 ms 51804 KB Output is correct
14 Correct 11 ms 51804 KB Output is correct
15 Correct 12 ms 51892 KB Output is correct
16 Correct 12 ms 51804 KB Output is correct
17 Correct 13 ms 51804 KB Output is correct
18 Correct 10 ms 51804 KB Output is correct
19 Correct 11 ms 51800 KB Output is correct
20 Correct 12 ms 51800 KB Output is correct
21 Correct 13 ms 51804 KB Output is correct
22 Correct 12 ms 51800 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51796 KB Output is correct
2 Correct 96 ms 69924 KB Output is correct
3 Correct 211 ms 69712 KB Output is correct
4 Correct 1278 ms 60256 KB Output is correct
5 Correct 167 ms 68988 KB Output is correct
6 Correct 114 ms 69232 KB Output is correct
7 Correct 804 ms 61032 KB Output is correct
8 Correct 1343 ms 61180 KB Output is correct
9 Correct 925 ms 60644 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 52056 KB Output is correct
2 Correct 813 ms 61184 KB Output is correct
3 Correct 1680 ms 60264 KB Output is correct
4 Correct 1224 ms 60268 KB Output is correct
5 Correct 1504 ms 61184 KB Output is correct
6 Execution timed out 2059 ms 60104 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 75632 KB Output is correct
2 Correct 250 ms 75640 KB Output is correct
3 Correct 122 ms 74832 KB Output is correct
4 Correct 127 ms 74832 KB Output is correct
5 Correct 206 ms 71508 KB Output is correct
6 Correct 273 ms 71740 KB Output is correct
7 Correct 279 ms 70532 KB Output is correct
8 Correct 171 ms 70224 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51796 KB Output is correct
2 Correct 13 ms 52056 KB Output is correct
3 Correct 10 ms 51908 KB Output is correct
4 Correct 10 ms 51804 KB Output is correct
5 Correct 12 ms 51884 KB Output is correct
6 Correct 11 ms 51804 KB Output is correct
7 Correct 10 ms 51688 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 12 ms 51804 KB Output is correct
10 Correct 10 ms 51916 KB Output is correct
11 Correct 11 ms 51804 KB Output is correct
12 Correct 10 ms 51804 KB Output is correct
13 Correct 11 ms 51804 KB Output is correct
14 Correct 11 ms 51804 KB Output is correct
15 Correct 12 ms 51892 KB Output is correct
16 Correct 12 ms 51804 KB Output is correct
17 Correct 13 ms 51804 KB Output is correct
18 Correct 10 ms 51804 KB Output is correct
19 Correct 11 ms 51800 KB Output is correct
20 Correct 12 ms 51800 KB Output is correct
21 Correct 13 ms 51804 KB Output is correct
22 Correct 12 ms 51800 KB Output is correct
23 Correct 74 ms 54576 KB Output is correct
24 Correct 56 ms 54440 KB Output is correct
25 Correct 68 ms 54488 KB Output is correct
26 Correct 126 ms 53484 KB Output is correct
27 Correct 124 ms 53484 KB Output is correct
28 Correct 187 ms 53472 KB Output is correct
29 Correct 225 ms 52940 KB Output is correct
30 Correct 199 ms 53332 KB Output is correct
31 Correct 183 ms 53464 KB Output is correct
32 Correct 19 ms 55416 KB Output is correct
33 Correct 105 ms 54392 KB Output is correct
34 Correct 171 ms 54404 KB Output is correct
35 Correct 104 ms 54332 KB Output is correct
36 Correct 265 ms 54364 KB Output is correct
37 Correct 285 ms 54364 KB Output is correct
38 Correct 251 ms 54408 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51796 KB Output is correct
2 Correct 13 ms 52056 KB Output is correct
3 Correct 10 ms 51908 KB Output is correct
4 Correct 10 ms 51804 KB Output is correct
5 Correct 12 ms 51884 KB Output is correct
6 Correct 11 ms 51804 KB Output is correct
7 Correct 10 ms 51688 KB Output is correct
8 Correct 11 ms 51804 KB Output is correct
9 Correct 12 ms 51804 KB Output is correct
10 Correct 10 ms 51916 KB Output is correct
11 Correct 11 ms 51804 KB Output is correct
12 Correct 10 ms 51804 KB Output is correct
13 Correct 11 ms 51804 KB Output is correct
14 Correct 11 ms 51804 KB Output is correct
15 Correct 12 ms 51892 KB Output is correct
16 Correct 12 ms 51804 KB Output is correct
17 Correct 13 ms 51804 KB Output is correct
18 Correct 10 ms 51804 KB Output is correct
19 Correct 11 ms 51800 KB Output is correct
20 Correct 12 ms 51800 KB Output is correct
21 Correct 13 ms 51804 KB Output is correct
22 Correct 12 ms 51800 KB Output is correct
23 Correct 96 ms 69924 KB Output is correct
24 Correct 211 ms 69712 KB Output is correct
25 Correct 1278 ms 60256 KB Output is correct
26 Correct 167 ms 68988 KB Output is correct
27 Correct 114 ms 69232 KB Output is correct
28 Correct 804 ms 61032 KB Output is correct
29 Correct 1343 ms 61180 KB Output is correct
30 Correct 925 ms 60644 KB Output is correct
31 Correct 813 ms 61184 KB Output is correct
32 Correct 1680 ms 60264 KB Output is correct
33 Correct 1224 ms 60268 KB Output is correct
34 Correct 1504 ms 61184 KB Output is correct
35 Execution timed out 2059 ms 60104 KB Time limit exceeded
36 Halted 0 ms 0 KB -