Submission #1253924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253924		nerrrmin	Fire (BOI24_fire)	C++20	0 / 100	376 ms	46052 KiB

Main

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

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

    cin >> n >> m;
    for (int 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());
    int 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 (int i = 1; i <= n; ++ i)
    {
        int l = mp[s[i]-1];
        int r = mp[e[i]];
       // cout << s[i]-1 << " ---> " << mp[s[i]-1] << endl;

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

    for (int i = lt; i <= rt; ++ i)
    {
       // cout << "left border " << endl;
        for (auto st: g[i])
        {
           // cout << st << endl;
            ql = st;
            qr = i;
            int 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