제출 #912398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
912398		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	196 ms	20608 KiB

triusis

#include <bits/stdc++.h>
#define f first
#define s second	
#define ent '\n'
#define int long long

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;
typedef long long ll;
const int mx=1e6+12;
const int mod=1e9+7;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};

int dp[5001][5001];
int tp[mx*4];
int t[mx*4];
int p[mx*4];
int a[mx];
int n,m,k;

void pull(int v,int tl,int tr,int type,int x){
	if(type==2){
		t[v]=x;
		p[v]=x;
		tp[v]=2;
	}
	else{
		t[v]+=x;
		p[v]+=x;
		if(tp[v]!=2)tp[v]=1;
	}
}
 
void push(int v,int tl,int tr){
	if(tl==tr || !tp[v])return;
	int mid=tl+tr>>1;
	pull(v*2,tl,mid,tp[v],p[v]);
	pull(v*2+1,mid+1,tr,tp[v],p[v]);
	tp[v]=0;
	p[v]=0;
}
 
void upd(int v,int tl,int tr,int l,int r,int x,int type){
	if(l>r)return;
	push(v,tl,tr);
	if(tl>r || l>tr)return;
	if(tl>=l && tr<=r){
		tp[v]=type;
		pull(v,tl,tr,tp[v],x);
		return;
	}
	int mid=tl+tr>>1;
	upd(v*2,tl,mid,l,r,x,type);
	upd(v*2+1,mid+1,tr,l,r,x,type);
	t[v]=max(t[v*2],t[v*2+1]);
}
 
int get(int v,int tl,int tr,int l,int r){
	push(v,tl,tr);
	if(tl>r || l>tr)return -1e18;
	if(tl>=l && tr<=r)return t[v];
	int mid=tl+tr>>1;
	return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}

int get(int v,int tl,int tr,int x){
	if(t[v]<x)return n+2;
	push(v,tl,tr);
	if(tl==tr){
		return tl;
	}
	int mid=tl+tr>>1;
	if(t[v*2]<x){
		return get(v*2+1,mid+1,tr,x);
	}
	return get(v*2,tl,mid,x);
}

void Press_Fn_with_F11(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	upd(1,0,n,0,n,-1e18,2);
	upd(1,0,n,n,n,0,2);
	for(int i=1;i<=n;i++){
		int pos=get(1,0,n,a[i]-m);
		if(pos>n)pos++;
		int x=get(1,0,n,n-i+1,n-i+1);
		upd(1,0,n,n-i+1,n,m,1);
		upd(1,0,n,pos-1,get(1,0,n,a[i]+1)-1,a[i],2);
		if(x+m>=a[i]){
			upd(1,0,n,n-i,n-i,a[i],2);
		}
	}
	cout<<get(1,0,n,0)<<ent;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int Alikhan_abi_crush=1;
	// cin>>Alikhan_abi_crush;
	while(Alikhan_abi_crush--){
		Press_Fn_with_F11();
	}
}

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

triusis.cpp: In function 'void push(long long int, long long int, long long int)':
triusis.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid=tl+tr>>1;
      |          ~~^~~
triusis.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
triusis.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int mid=tl+tr>>1;
      |          ~~^~~
triusis.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
triusis.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int mid=tl+tr>>1;
      |          ~~^~~
triusis.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
triusis.cpp:75:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |  int mid=tl+tr>>1;
      |          ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37