제출 #870812

#제출 시각아이디문제언어결과실행 시간메모리
870812salmon서열 (APIO23_sequence)C++17
100 / 100
772 ms70792 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; int N; int miin[500100 * 4]; int maax[500100 * 4]; int lazy[500100 * 4]; int miin1[500100 * 4]; int maax1[500100 * 4]; int lazy1[500100 * 4]; vector<int> in[500100]; vector<int> sat; void build(int i, int s, int e, int *miin, int *maax, int *lazy){ miin[i] = - e - 1; maax[i] = - s - 1; lazy[i] = 0; if(s != e){ int m = (s + e + 2)/2 - 1; build(i * 2, s, m, miin, maax, lazy); build(i * 2 + 1, m + 1, e, miin, maax, lazy); } } void update(int i, int s, int e, int S, int *miin, int *maax, int *lazy){ if(S <= s){ miin[i] += 2; maax[i] += 2; lazy[i] += 2; return; } int m = (s + e + 2)/2 - 1; update(i * 2 + 1, m + 1, e, S, miin, maax, lazy); if(S <= m){ update(i * 2, s, m, S, miin, maax, lazy); } miin[i] = min(miin[i * 2], miin[i * 2 + 1]) + lazy[i]; maax[i] = max(maax[i * 2], maax[i * 2 + 1]) + lazy[i]; } pair<int,int> query(int i, int s, int e, int S, int E, int *miin, int *maax, int *lazy){ if(S <= s && e <= E){ return make_pair(miin[i],maax[i]); } int m = (s + e + 2)/2 - 1; pair<int,int> ii,ii1; if(S <= m && m < E){ ii = query(i * 2, s, m, S, E, miin, maax, lazy); ii1 = query(i * 2 + 1, m + 1, e, S, E, miin, maax, lazy); ii.first = min(ii.first, ii1.first) + lazy[i]; ii.second = max(ii.second, ii1.second) + lazy[i]; } else if(S <= m){ ii = query(i * 2, s, m, S, E, miin, maax, lazy); ii.first = ii.first + lazy[i]; ii.second = ii.second + lazy[i]; } else{ ii = query(i * 2 + 1, m + 1, e, S, E, miin, maax, lazy); ii.first = ii.first + lazy[i]; ii.second = ii.second + lazy[i]; } return ii; } int sequence(int N, std::vector<int> lst) { for(int i = 0; i < N; i++){ in[lst[i]].push_back(i); } build(1,-1,N-1,miin1,maax1,lazy1); build(1,-1,N-1,miin,maax,lazy); bool flag = false; int ans = 0; for(int i = 1; i <= N; i++){ sat.clear(); sat.push_back(-1); for(int j = 0; j < in[i].size(); j++){ sat.push_back(in[i][j]); } sat.push_back(N); for(int j = 0; j < in[i].size() ; j++){ update(1,-1,N-1,in[i][j],miin,maax,lazy); } for(int j = 1; j <= in[i].size(); j++){ int small = query(1, -1, N - 1, -1, sat[j] - 1, miin, maax, lazy).first; int big1 = query(1, -1, N - 1, -1, sat[j] - 1, miin1, maax1, lazy1).second; int l,r,m,s,e; int eye; eye = 1; l = sat[j]; r = N - 1; s = -1; e = N - 1; int lacy = 0; int lacy1 = 0; while(s != e){ m = (s + e)/2; lacy += lazy[eye]; lacy1 += lazy1[eye]; if(m < l){ s = m + 1; eye = eye * 2 + 1; continue; } if((maax[eye * 2 + 1] + lacy - small) * (long long int)(miin1[eye * 2 + 1] + lacy1 - big1) <= 0){ s = m + 1; eye = eye * 2 + 1; continue; } else{ e = m; eye = eye * 2; } } auto it = upper_bound(sat.begin(),sat.end(),s); it--; ans = max(ans,(int)(it - sat.begin()) - j + 1); } for(int j = 0; j < in[i].size() ; j++){ update(1,-1,N-1,in[i][j],miin1,maax1,lazy1); } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j = 0; j < in[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~
sequence.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int j = 0; j < in[i].size() ; j++){
      |                        ~~^~~~~~~~~~~~~~
sequence.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int j = 1; j <= in[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
sequence.cpp:109:19: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  109 |             int l,r,m,s,e;
      |                   ^
sequence.cpp:151:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for(int j = 0; j < in[i].size() ; j++){
      |                        ~~^~~~~~~~~~~~~~
sequence.cpp:87:10: warning: unused variable 'flag' [-Wunused-variable]
   87 |     bool flag = false;
      |          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...