제출 #1253925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253925		nerrrmin	Fire (BOI24_fire)	C++20	0 / 100	434 ms	72732 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const long long maxn = 1e6 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m;
long long s[maxn], e[maxn];
map < long long, long long > mp;
vector < long long > u;

long long t[maxn * 4];
long long dp[maxn];
void build(long long i, long long l, long long r)
{
    t[i] = 1e9;
    if(l == r)
    {
        dp[l] = 1e9;
        return;
    }
    long long mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
}
long long ql, qr;
long long query(long long i, long long l, long long r)
{
    if(qr < l || ql > r)return 1e9;
    if(ql <= l && r <= qr)return t[i];
    long long mid = (l + r)/2;
    return min(query(2*i, l, mid), query(2*i+1, mid+1, r));
}
long long upos, uval;
void update(long long i, long long l, long long r)
{
    if(l == r)
    {
        dp[l] = min(dp[l], uval);
        t[i] = min(t[i], uval);
        return;
    }
    long long mid = (l + r)/2;
    if(upos <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = min(t[2*i], t[2*i+1]);
   // cout << endl;
   // cout << t[i] << endl;
}
vector < long long > g[maxn];
int main()
{
    speed();

    cin >> n >> m;
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> s[i] >> e[i];
        if(!e[i])e[i] = m;
        u.pb(s[i]-1);
        u.pb(e[i]);
    }
    u.pb(-1);

    u.pb(0);
    u.pb(m);
    sort(u.begin(), u.end());
    long long last = -2, cnt = 0;
    for (auto x: u)
    {


        if(last != x)
        {
          //  cout <<  x << " is transf to " << cnt << endl;

            mp[x] = cnt;
            cnt ++;
        }
        last = x;
    }
    for (long long i = 1; i <= n; ++ i)
    {
        long long l = mp[s[i]-1];
        long long r = mp[e[i]];
       // cout << s[i]-1 << " ---> " << mp[s[i]-1] << endl;

        g[r].pb(l);
    }
    long long lt = mp[0], rt = mp[m];
    long long l = mp[-1];
    build(1, l, rt);
    dp[l] = 0;
    upos = l;
    uval = 0;
    update(1, l, rt);

    for (long long i = lt; i <= rt; ++ i)
    {
       // cout << "left border " << endl;
        for (auto st: g[i])
        {
           // cout << st << endl;
            ql = st;
            qr = i;
            long long val = query(1, l, rt);
           // cout << "^^^^^ " << val << endl;
            dp[i] = min(dp[i], val + 1);
            uval = dp[i];
            upos = i;
            update(1, l, rt);
        }

       // cout << "dp[i] with i = " << i << " is " << dp[i] << endl;
    }
    if(dp[rt] == 1e9)cout << -1 << endl;
    else cout << dp[rt] << endl;
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26