제출 #1146764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146764		Newtonabc	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	328 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int arr[N];
set<pair<int,int>> s;
int cp(pair<int,int> a,pair<int,int> b){
    //compare a better 1, equal 0 , b better -1
    if(a.first>b.first){
        if(a.second>=b.second) return 1;
        else return 0;
    }
    if(a.first==b.first){
        if(a.second>b.second) return 1;
        else if(a.second==b.second) return 0;
        else return -1;
    }
    if(a.first<b.first){
        if(b.second>=a.second) return -1;
        return 0;
    }
}
void pt(){
    cout<<"---------" <<"\n";
    for(auto it=s.begin();it!=s.end();it++){
        cout<<it->first <<" " <<it->second <<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n >>m;
    for(int i=1;i<=n;i++) cin>>arr[i];
    s.insert({0,0});
    for(int i=1;i<=n;i++){
        //pt();
        auto it=s.lower_bound({arr[i]-m,INT_MIN});
        if(it==s.end()) continue;
        //height=arr[i],block picked=find+1
        int pick=it->second+1;
        pair<int,int> tmp={arr[i],pick};
        s.insert(tmp);
        it=s.find(tmp);
        auto c=it;
        //check if can put in the set
        if(it!=s.begin()){
            c--;
            if(cp(tmp,*c)==-1){
                s.erase(tmp);
                continue;
            }
        }
        c=it,c++;
        if(c!=s.end()){
            if(cp(tmp,*c)==-1){
                s.erase(tmp);
                continue;
            }
        }
        //erase the other
        while(it!=s.begin()){
            c=it,c--;
            if(cp(tmp,*c)==1) s.erase(c);
            else break;
        }
        c=it,c++;
        while(c!=s.end()){
            if(cp(tmp,*c)==1) s.erase(c);
            else break;
            c=it,c++;
        }
    }
    //pt();
    int ans=s.begin()->second;
    cout<<n-ans;
}

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

triusis.cpp: In function 'int cp(std::pair<int, int>, std::pair<int, int>)':
triusis.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

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