oj.uz

답안 #979838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979838 2024-05-11T13:27:32 Z AlperenT_ 서열 (APIO23_sequence) C++17
70 / 100
 2000 ms 128084 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(j!=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

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 103004 KB Output is correct
2 Correct 20 ms 103004 KB Output is correct
3 Correct 20 ms 103184 KB Output is correct
4 Correct 20 ms 103004 KB Output is correct
5 Correct 19 ms 102976 KB Output is correct
6 Correct 20 ms 103252 KB Output is correct
7 Correct 20 ms 103188 KB Output is correct
8 Correct 19 ms 103256 KB Output is correct
9 Correct 20 ms 103180 KB Output is correct
10 Correct 20 ms 103004 KB Output is correct
11 Correct 20 ms 103004 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 103004 KB Output is correct
2 Correct 20 ms 103004 KB Output is correct
3 Correct 20 ms 103184 KB Output is correct
4 Correct 20 ms 103004 KB Output is correct
5 Correct 19 ms 102976 KB Output is correct
6 Correct 20 ms 103252 KB Output is correct
7 Correct 20 ms 103188 KB Output is correct
8 Correct 19 ms 103256 KB Output is correct
9 Correct 20 ms 103180 KB Output is correct
10 Correct 20 ms 103004 KB Output is correct
11 Correct 20 ms 103004 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct
13 Correct 21 ms 103256 KB Output is correct
14 Correct 22 ms 103260 KB Output is correct
15 Correct 22 ms 103212 KB Output is correct
16 Correct 22 ms 103004 KB Output is correct
17 Correct 23 ms 103188 KB Output is correct
18 Correct 21 ms 103256 KB Output is correct
19 Correct 22 ms 103248 KB Output is correct
20 Correct 21 ms 103456 KB Output is correct
21 Correct 23 ms 103260 KB Output is correct
22 Correct 22 ms 103212 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 103004 KB Output is correct
2 Correct 101 ms 121896 KB Output is correct
3 Correct 229 ms 122196 KB Output is correct
4 Correct 1305 ms 112248 KB Output is correct
5 Correct 170 ms 121168 KB Output is correct
6 Correct 117 ms 121172 KB Output is correct
7 Correct 822 ms 113232 KB Output is correct
8 Correct 1450 ms 113172 KB Output is correct
9 Correct 975 ms 112800 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 103004 KB Output is correct
2 Correct 850 ms 113156 KB Output is correct
3 Correct 1708 ms 112328 KB Output is correct
4 Correct 1206 ms 112772 KB Output is correct
5 Correct 1505 ms 113132 KB Output is correct
6 Execution timed out 2052 ms 112316 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 127568 KB Output is correct
2 Correct 234 ms 128084 KB Output is correct
3 Correct 142 ms 127572 KB Output is correct
4 Correct 136 ms 127532 KB Output is correct
5 Correct 222 ms 124120 KB Output is correct
6 Correct 292 ms 124124 KB Output is correct
7 Correct 271 ms 122924 KB Output is correct
8 Correct 184 ms 122436 KB Output is correct

Subtask #6
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 103004 KB Output is correct
2 Correct 20 ms 103004 KB Output is correct
3 Correct 20 ms 103184 KB Output is correct
4 Correct 20 ms 103004 KB Output is correct
5 Correct 19 ms 102976 KB Output is correct
6 Correct 20 ms 103252 KB Output is correct
7 Correct 20 ms 103188 KB Output is correct
8 Correct 19 ms 103256 KB Output is correct
9 Correct 20 ms 103180 KB Output is correct
10 Correct 20 ms 103004 KB Output is correct
11 Correct 20 ms 103004 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct
13 Correct 21 ms 103256 KB Output is correct
14 Correct 22 ms 103260 KB Output is correct
15 Correct 22 ms 103212 KB Output is correct
16 Correct 22 ms 103004 KB Output is correct
17 Correct 23 ms 103188 KB Output is correct
18 Correct 21 ms 103256 KB Output is correct
19 Correct 22 ms 103248 KB Output is correct
20 Correct 21 ms 103456 KB Output is correct
21 Correct 23 ms 103260 KB Output is correct
22 Correct 22 ms 103212 KB Output is correct
23 Correct 74 ms 105876 KB Output is correct
24 Correct 68 ms 105816 KB Output is correct
25 Correct 70 ms 105812 KB Output is correct
26 Correct 160 ms 104780 KB Output is correct
27 Correct 135 ms 104796 KB Output is correct
28 Correct 186 ms 104796 KB Output is correct
29 Correct 241 ms 104392 KB Output is correct
30 Correct 221 ms 104456 KB Output is correct
31 Correct 193 ms 104912 KB Output is correct
32 Correct 29 ms 106588 KB Output is correct
33 Correct 118 ms 105484 KB Output is correct
34 Correct 187 ms 105524 KB Output is correct
35 Correct 115 ms 105644 KB Output is correct
36 Correct 285 ms 105652 KB Output is correct
37 Correct 288 ms 105672 KB Output is correct
38 Correct 288 ms 105712 KB Output is correct

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 103004 KB Output is correct
2 Correct 20 ms 103004 KB Output is correct
3 Correct 20 ms 103184 KB Output is correct
4 Correct 20 ms 103004 KB Output is correct
5 Correct 19 ms 102976 KB Output is correct
6 Correct 20 ms 103252 KB Output is correct
7 Correct 20 ms 103188 KB Output is correct
8 Correct 19 ms 103256 KB Output is correct
9 Correct 20 ms 103180 KB Output is correct
10 Correct 20 ms 103004 KB Output is correct
11 Correct 20 ms 103004 KB Output is correct
12 Correct 20 ms 103004 KB Output is correct
13 Correct 21 ms 103256 KB Output is correct
14 Correct 22 ms 103260 KB Output is correct
15 Correct 22 ms 103212 KB Output is correct
16 Correct 22 ms 103004 KB Output is correct
17 Correct 23 ms 103188 KB Output is correct
18 Correct 21 ms 103256 KB Output is correct
19 Correct 22 ms 103248 KB Output is correct
20 Correct 21 ms 103456 KB Output is correct
21 Correct 23 ms 103260 KB Output is correct
22 Correct 22 ms 103212 KB Output is correct
23 Correct 101 ms 121896 KB Output is correct
24 Correct 229 ms 122196 KB Output is correct
25 Correct 1305 ms 112248 KB Output is correct
26 Correct 170 ms 121168 KB Output is correct
27 Correct 117 ms 121172 KB Output is correct
28 Correct 822 ms 113232 KB Output is correct
29 Correct 1450 ms 113172 KB Output is correct
30 Correct 975 ms 112800 KB Output is correct
31 Correct 850 ms 113156 KB Output is correct
32 Correct 1708 ms 112328 KB Output is correct
33 Correct 1206 ms 112772 KB Output is correct
34 Correct 1505 ms 113132 KB Output is correct
35 Execution timed out 2052 ms 112316 KB Time limit exceeded
36 Halted 0 ms 0 KB -