oj.uz

Submission #978318

# Submission time Handle Problem Language Result Execution time Memory
978318 2024-05-09T06:15:55 Z AlperenT_ Sequence (APIO23_sequence) C++17
57 / 100
 2000 ms 127040 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) ;
    if(a[i] > n)cout << 1/0 ; 
  }
  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;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:122:26: warning: division by zero [-Wdiv-by-zero]
  122 |     if(a[i] > n)cout << 1/0 ;
      |                         ~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 101972 KB Output is correct
2 Correct 41 ms 101980 KB Output is correct
3 Correct 42 ms 101976 KB Output is correct
4 Correct 41 ms 101968 KB Output is correct
5 Correct 50 ms 102156 KB Output is correct
6 Correct 46 ms 101968 KB Output is correct
7 Correct 41 ms 102184 KB Output is correct
8 Correct 42 ms 101972 KB Output is correct
9 Correct 41 ms 101980 KB Output is correct
10 Correct 41 ms 101972 KB Output is correct
11 Correct 46 ms 101968 KB Output is correct
12 Correct 41 ms 101976 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 101972 KB Output is correct
2 Correct 41 ms 101980 KB Output is correct
3 Correct 42 ms 101976 KB Output is correct
4 Correct 41 ms 101968 KB Output is correct
5 Correct 50 ms 102156 KB Output is correct
6 Correct 46 ms 101968 KB Output is correct
7 Correct 41 ms 102184 KB Output is correct
8 Correct 42 ms 101972 KB Output is correct
9 Correct 41 ms 101980 KB Output is correct
10 Correct 41 ms 101972 KB Output is correct
11 Correct 46 ms 101968 KB Output is correct
12 Correct 41 ms 101976 KB Output is correct
13 Correct 41 ms 102184 KB Output is correct
14 Correct 42 ms 102224 KB Output is correct
15 Correct 43 ms 102224 KB Output is correct
16 Correct 43 ms 102076 KB Output is correct
17 Correct 45 ms 102228 KB Output is correct
18 Correct 42 ms 102092 KB Output is correct
19 Correct 42 ms 102228 KB Output is correct
20 Correct 46 ms 102228 KB Output is correct
21 Correct 45 ms 102132 KB Output is correct
22 Correct 47 ms 102224 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 101972 KB Output is correct
2 Correct 123 ms 121160 KB Output is correct
3 Correct 269 ms 121308 KB Output is correct
4 Correct 1345 ms 111152 KB Output is correct
5 Correct 197 ms 120276 KB Output is correct
6 Correct 140 ms 120144 KB Output is correct
7 Correct 846 ms 111700 KB Output is correct
8 Correct 1513 ms 112204 KB Output is correct
9 Correct 975 ms 111588 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 101980 KB Output is correct
2 Correct 911 ms 111968 KB Output is correct
3 Correct 1827 ms 111160 KB Output is correct
4 Correct 1409 ms 111160 KB Output is correct
5 Correct 1627 ms 112048 KB Output is correct
6 Execution timed out 2057 ms 111228 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 127040 KB Output is correct
2 Correct 272 ms 127028 KB Output is correct
3 Correct 163 ms 126288 KB Output is correct
4 Correct 165 ms 126296 KB Output is correct
5 Incorrect 351 ms 123016 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 43 ms 101972 KB Output is correct
2 Correct 41 ms 101980 KB Output is correct
3 Correct 42 ms 101976 KB Output is correct
4 Correct 41 ms 101968 KB Output is correct
5 Correct 50 ms 102156 KB Output is correct
6 Correct 46 ms 101968 KB Output is correct
7 Correct 41 ms 102184 KB Output is correct
8 Correct 42 ms 101972 KB Output is correct
9 Correct 41 ms 101980 KB Output is correct
10 Correct 41 ms 101972 KB Output is correct
11 Correct 46 ms 101968 KB Output is correct
12 Correct 41 ms 101976 KB Output is correct
13 Correct 41 ms 102184 KB Output is correct
14 Correct 42 ms 102224 KB Output is correct
15 Correct 43 ms 102224 KB Output is correct
16 Correct 43 ms 102076 KB Output is correct
17 Correct 45 ms 102228 KB Output is correct
18 Correct 42 ms 102092 KB Output is correct
19 Correct 42 ms 102228 KB Output is correct
20 Correct 46 ms 102228 KB Output is correct
21 Correct 45 ms 102132 KB Output is correct
22 Correct 47 ms 102224 KB Output is correct
23 Correct 95 ms 105040 KB Output is correct
24 Correct 91 ms 105296 KB Output is correct
25 Correct 107 ms 105044 KB Output is correct
26 Correct 161 ms 104020 KB Output is correct
27 Correct 155 ms 103996 KB Output is correct
28 Correct 209 ms 104024 KB Output is correct
29 Correct 266 ms 103704 KB Output is correct
30 Correct 241 ms 103764 KB Output is correct
31 Correct 220 ms 104020 KB Output is correct
32 Correct 52 ms 106064 KB Output is correct
33 Correct 135 ms 105008 KB Output is correct
34 Correct 199 ms 105016 KB Output is correct
35 Correct 143 ms 104956 KB Output is correct
36 Correct 306 ms 104800 KB Output is correct
37 Correct 296 ms 104860 KB Output is correct
38 Correct 301 ms 105016 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 101972 KB Output is correct
2 Correct 41 ms 101980 KB Output is correct
3 Correct 42 ms 101976 KB Output is correct
4 Correct 41 ms 101968 KB Output is correct
5 Correct 50 ms 102156 KB Output is correct
6 Correct 46 ms 101968 KB Output is correct
7 Correct 41 ms 102184 KB Output is correct
8 Correct 42 ms 101972 KB Output is correct
9 Correct 41 ms 101980 KB Output is correct
10 Correct 41 ms 101972 KB Output is correct
11 Correct 46 ms 101968 KB Output is correct
12 Correct 41 ms 101976 KB Output is correct
13 Correct 41 ms 102184 KB Output is correct
14 Correct 42 ms 102224 KB Output is correct
15 Correct 43 ms 102224 KB Output is correct
16 Correct 43 ms 102076 KB Output is correct
17 Correct 45 ms 102228 KB Output is correct
18 Correct 42 ms 102092 KB Output is correct
19 Correct 42 ms 102228 KB Output is correct
20 Correct 46 ms 102228 KB Output is correct
21 Correct 45 ms 102132 KB Output is correct
22 Correct 47 ms 102224 KB Output is correct
23 Correct 123 ms 121160 KB Output is correct
24 Correct 269 ms 121308 KB Output is correct
25 Correct 1345 ms 111152 KB Output is correct
26 Correct 197 ms 120276 KB Output is correct
27 Correct 140 ms 120144 KB Output is correct
28 Correct 846 ms 111700 KB Output is correct
29 Correct 1513 ms 112204 KB Output is correct
30 Correct 975 ms 111588 KB Output is correct
31 Correct 911 ms 111968 KB Output is correct
32 Correct 1827 ms 111160 KB Output is correct
33 Correct 1409 ms 111160 KB Output is correct
34 Correct 1627 ms 112048 KB Output is correct
35 Execution timed out 2057 ms 111228 KB Time limit exceeded
36 Halted 0 ms 0 KB -