이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// n valores
// qr escolher m p apresentar - a dif de 2 adjs n pode ser maior que d
// o ultimo a ser mostrado é pm = n (o ultimo cara smp aparece)
// score é o n° vzs q o at eh maior que o pref dele + 1
#include<bits/stdc++.h>
#define esq (2*no)
#define dir ((2*no)+1)
#define meio ((i+j)>>1)
#define int long long
using namespace std ;
// qual o 1o maior p cada cara - esquerda
const int inf = 1e13 ;
const int maxn = 3e5 + 5 ;
int n, mx[maxn], d, v[maxn], esqq[maxn] ;
int tree[4*maxn] ;
void sub1(){
int ans = 0 ;
int tryy = (1<<7) + (1<<6) + (1<<5) + (1<<4);
for(int mask = 0 ; mask < (1<<(n+1)) ; mask++){
if(mask&(1<<0)) continue ;
vector<int> vec ;
// cout << mask << "\n" ;
for(int i = 1 ; i < n + 1 ; i++){
if(mask&(1<<i)) vec.push_back(i) ;
}
bool ok = 1 ;
for(int i = 1 ; i < vec.size() ; i++) if(vec[i] - vec[i-1] > d) ok = 0 ;
if(!ok) continue ;
for(int i = 0 ; i < vec.size() ; i++){
int fmx = -1 ;
for(int j = i - 1 ; j >= 0 ; j--){
if(v[vec[j]] >= v[vec[i]]){fmx = j ; break ;}
}
esqq[i] = fmx ;
}
int sm = 0 ;
for(int i = 0 ; i < vec.size() ; i++) sm += (esqq[i]==-1) ;
// for(auto a : vec) cout << a << " " ;
// cout << "\n" ;
// for(int i = 0 ; i < vec.size() ; i++) cout << esq[i] << " " ;
// cout << "\n" ;
// cout << sm << "\n" ;
ans = max(ans, sm) ;
}
cout << ans << "\n" ;
}
// dp[i][d] - maior valor até i sendo d o ultimo usado
struct SEG{
// lis -> muda a pos do valor + 1 e query 1, no meu - 1
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]) ;
}
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 ;
void sub2(){
// d == n -> maior lis
int ans = 0 ;
for(int i = 1 ; i <= n ; i++){
int at = Seg.query(1, 1, n, 1, i-1) + 1 ;
Seg.upd(1, 1, n, i, at+1) ;
ans = max(ans, at) ;
}
cout << ans << "\n" ;
}
int32_t 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 ;
if(n <= 20) sub1() ;
else sub2() ;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void sub1()':
Main.cpp:33:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 1 ; i < vec.size() ; i++) if(vec[i] - vec[i-1] > d) ok = 0 ;
| ~~^~~~~~~~~~~~
Main.cpp:35:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0 ; i < vec.size() ; i++){
| ~~^~~~~~~~~~~~
Main.cpp:43:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0 ; i < vec.size() ; i++) sm += (esqq[i]==-1) ;
| ~~^~~~~~~~~~~~
Main.cpp:23:9: warning: unused variable 'tryy' [-Wunused-variable]
23 | int tryy = (1<<7) + (1<<6) + (1<<5) + (1<<4);
| ^~~~
# | 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... |