이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define esq (2*no)
#define dir ((2*no)+1)
#define meio ((i+j)>>1)
using namespace std ;
// mantenho num vetor os kras q eu add - preciso mudar tds os caras q eu n atualizei desde o kra q eu to vendo
// se essa dist passar de d
const int maxn = 3e5 + 5 ;
int n, d, v[maxn], lst_app[maxn], lst[maxn] ;
int tree[4*maxn] ;
struct SEG{
void upd(int no, int i, int j, int pos, int val){
if(i == j){
tree[no] = max(tree[no], val) ; return ;
}
if(pos <= meio) upd(esq, i, meio, pos, val) ;
else upd(dir, meio + 1, j, pos, val) ;
tree[no] = max(tree[esq], tree[dir]) ;
}
void upd2(int no, int i, int j, int pos, int val){
if(i == j){
tree[no] = val ; return ;
}
if(pos <= meio) upd2(esq, i, meio, pos, val) ;
else upd2(dir, meio + 1, j, pos, val) ;
tree[no] = max(tree[esq], tree[dir]) ;
}
int query(int no, int i, int j, int a, int b){
if(a > j || b < i) return 0 ;
if(b >= j && a <= i) return tree[no] ;
return max(query(esq, i, meio, a, b), query(dir, meio + 1, j, a, b)) ;
}
} Seg ;
int main(){
cin >> n >> d ;
vector<int> vec ;
for(int i = 1 ; i <= n ; i++){
cin >> v[i] ;
vec.push_back(v[i]) ;
}
sort(vec.begin(), vec.end()) ;
for(int i = 1 ; i <= n ; i++) v[i] = lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin() + 1 ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; ; j++){
if(i-j <= d) break ;
if(lst_app[v[j]] == j){
// cout << i << " " << j << " " << lst[v[j]] << "\n" ;
Seg.upd2(1, 1, n, v[j], lst[v[j]]) ;
lst_app[v[j]] = 0 ;
// cout << Seg.query(1, 1, n, v[j], v[j]) << "\n" ;
}
}
int att = Seg.query(1, 1, n, 1, v[i]-1) ;
// cout << i << " " << att << "\n" ;
int ant = Seg.query(1, 1, n, v[i], v[i]) ;
if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
ans = max(ans, att + 1) ;
Seg.upd(1, 1, n, v[i], att + 1) ;
}
cout << ans << "\n" ;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:73:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
73 | if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
| ^~
Main.cpp:73:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
73 | if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
| ^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |