이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct lisan{
vector<int>vt;
void in(int x){ vt.push_back(x); }
void build(){
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
}
int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
}uni;
vector<int>no;
struct not_bigest_segtree{
int mn[4*N],tag[4*N];
bool surv[4*N];
void push(int i){
if (tag[i]){
tag[2*i]=tag[i];
tag[2*i+1]=tag[i];
mn[2*i]=tag[i];
mn[2*i+1]=tag[i];
tag[i]=0;
}
}
void dfs(int l,int r,int i,int p,int d){
if (l==r){
no.push_back(l);
surv[i]=0; mn[i]=1e9;
return;
}
int mid=(l+r)>>1;
push(i);
if (mn[2*i]<p-d&&surv[2*i]) dfs(l,mid,2*i,p,d);
if (mn[2*i+1]<p-d&&surv[2*i+1]) dfs(mid+1,r,2*i+1,p,d);
mn[i]=min(mn[2*i],mn[2*i+1]);
surv[i]=(surv[2*i]|surv[2*i+1]);
}
void add(int l,int r,int i,int p){
if (l==r){
surv[i]=1;
return;
}
int mid=(l+r)>>1;
push(i);
if (p<=mid) add(l,mid,2*i,p);
else add(mid+1,r,2*i+1,p);
surv[i]=(surv[2*i]|surv[2*i+1]);
}
void modify(int l,int r,int i,int ll,int rr,int val){
if (ll>rr) return;
if (!surv[i]) return;
if (ll<=l&&rr>=r){
if (surv[i]){
tag[i]=val; mn[i]=val;
}
return;
}
int mid=(l+r)>>1;
push(i);
if (rr<=mid) modify(l,mid,2*i,ll,rr,val);
else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,val);
else {
modify(l,mid,2*i,ll,rr,val);
modify(mid+1,r,2*i+1,ll,rr,val);
}
mn[i]=min(mn[2*i],mn[2*i+1]);
}
}surv;
struct is_bigest_segtree{
int mx[4*N];
void modify(int l,int r,int i,int p,int val,bool flag){
if (l==r){
if (flag) mx[i]=val;
else mx[i]=max(val,mx[i]);
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(l,mid,2*i,p,val,flag);
else modify(mid+1,r,2*i+1,p,val,flag);
mx[i]=max(mx[2*i],mx[2*i+1]);
}
int query(int l,int r,int i,int ll,int rr){
if (ll>rr) return 0;
if (ll<=l&&rr>=r) return mx[i];
int mid=(l+r)>>1;
if (rr<=mid) return query(l,mid,2*i,ll,rr);
else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
else return max(query(l,mid,2*i,ll,rr),query(mid+1,r,2*i+1,ll,rr));
}
}seg;
int dp[N],n,d,a[N];
signed main(){
fast
cin>>n>>d;
for (int i=1;i<=n;i++){
cin>>a[i];
uni.in(a[i]);
}
uni.build();
for (int i=1;i<=n;i++)
a[i]=uni.idx(a[i]);
for (int i=1;i<=n;i++){
surv.dfs(1,n,1,i,d);
for (auto j:no){
seg.modify(1,n,1,j,0,1);
}
no.clear();
dp[i]=seg.query(1,n,1,1,a[i]-1)+1;
surv.add(1,n,1,a[i]);
surv.modify(1,n,1,a[i],n,i);
seg.modify(1,n,1,a[i],dp[i],0);
}
int ans=1;
for (int i=1;i<=n;i++)
ans=max(ans,dp[i]);
cout<<ans<<'\n';
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
| ^
Main.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
Main.cpp:18:18: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
18 | void in(int x){ vt.push_back(x); }
| ^
Main.cpp:18:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:18:18: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
19 | void build(){
| ^
Main.cpp:19:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:19:16: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
23 | int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
| ^
Main.cpp:23:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:23:18: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
29 | void push(int i){
| ^
Main.cpp:29:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:29:20: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
38 | void dfs(int l,int r,int i,int p,int d){
| ^
Main.cpp:38:43: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:38:43: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
51 | void add(int l,int r,int i,int p){
| ^
Main.cpp:51:37: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:51:37: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
62 | void modify(int l,int r,int i,int ll,int rr,int val){
| ^
Main.cpp:62:56: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:62:56: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
84 | void modify(int l,int r,int i,int p,int val,bool flag){
| ^
Main.cpp:84:58: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:84:58: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
95 | int query(int l,int r,int i,int ll,int rr){
| ^
Main.cpp:95:46: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:95:46: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
105 | signed main(){
| ^
Main.cpp:105:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
Main.cpp:105:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]| # | 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... |
