제출 #1287642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287642		mattgryts	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	183 ms	47324 KiB

Main

//Denysiuk Illia will win EJOI 2026
//Denysiuk Illia will win UJGOI 2026
//Антон Перебейнис ничего не ботал
#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <functional>
using namespace std;
const long long INF=1e17;
const long long mod=1e9+7;
const long long maxlog=22;
using victor = vector<int>;

using dih = deque<int>;
using pll=pair<long long,long long>;
using ll = long long;
using victor = vector<int>;
using victorl =vector<long long>;
using victorll = vector<pll>;
const int NIGGA=2*1e5+10;
ll ceil(ll a,ll b){
    return max((ll)0,(a+b-1)/b);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    victorll a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;

    sort(begin(a),end(a));
    victorl d(n+100),s(n+100);
    for(int i=1;i<=n;i++){
        d[i]=a[i].first-a[i].second;
        s[i]=a[i].first+a[i].second;
    }
    victor L(n+10,0),R(n+10,n+1);
    for(int i=1;i<=n;i++){
        L[i]=i-1;
        R[i]=i+1;
    }
    stack<int>st;
   for(int i=n;i>=1;i--){
        while(!st.empty() && d[i]<d[st.top()]){
            L[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()){
        L[st.top()]=0;
        st.pop();
    }
    while(!st.empty())st.pop();
    for(int i=1;i<=n;i++){
        while(!st.empty() && s[i]>s[st.top()]){
            R[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()){
        R[st.top()]=n+1;
        st.pop();
    }
   vector<victor>g(n+1);

   for(int i=1;i<=n;i++)g[L[i]+1].push_back(R[i]-1);
   int ans=0;
   int ptr=1;
   priority_queue<int>pq;
   while(ptr<=n){
    for(auto x:g[ptr])pq.push(x);
    int r=pq.top();
    while(!pq.empty())pq.pop();
    ++ptr;
    while(ptr<=r){
        for(auto x:g[ptr])pq.push(x);
        ptr++;
    }
    ans++;
   }
   cout<<ans<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31