제출 #1118509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118509		lampooppp	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1020 ms	58028 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=5e5;
map<int,int> mp;
int val[N+1];
//nen x
pair<int,int> p[N+1];

bool took[N+1];

struct event
{
    int tme, id;
    bool operator < (const event & o) const
    {
        return tme < o.tme;
    }
};

priority_queue<event> pq;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;++i)
    {
        cin >> p[i].second >> p[i].first;
        mp[p[i].second]=0;
    }
    int tme=0;
    for(auto& k : mp)
    {
        val[++tme] = k.first;
        k.second=tme;
    }
    sort(p+1,p+n+1);
    //priority_queue<pair<int,int>>
    int cnt=0;
    for(int i=n;i>0;--i)
    {
        p[i].second=mp[p[i].second];
        //cout << "SET " << p[i].first << " :\n";
        while(!pq.empty() && pq.top().tme>=p[i].first)
        {
            auto k = pq.top();
            pq.pop();
            if(took[k.id]==1) continue;
            //cout << k.id << " " << k.tme << '\n';
            took[k.id]=1;
            if(k.id>1 && !took[k.id-1])
            {
                int tme = k.tme - (val[k.id]-val[k.id-1]);
                pq.push({tme,k.id-1});
            }
            if(k.id<n && !took[k.id+1])
            {
                int tme = k.tme- (- val[k.id]+val[k.id+1]);
                pq.push({tme,k.id+1});
            }
        }
        if(!took[p[i].second])
        {
            //cout << i << "L";
            pq.push({p[i].first,p[i].second});
            cnt++;
        }
    }
    cout << cnt;

}

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