Submission #1104549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104549		12345678	Fire (BOI24_fire)	C++17	100 / 100	1168 ms	173628 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int nx=2e5+5, kx=18;

ll n, m, pa[nx][kx], sm[nx][kx], t, vl[nx][2], sh[nx][2], svl[nx][2], ssh[nx][2], ans=1e9;
map<ll, ll> mp;

struct segtree
{
    tuple<ll, ll, ll> d[16*nx];
    void update(int l, int r, int i, int idx, tuple<ll, ll, ll> vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=max(d[i], vl), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }  
    tuple<ll, ll, ll> query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return {0, 0, 0};
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        cin>>vl[i][0]>>vl[i][1];
        if (vl[i][1]<vl[i][0]) vl[i][1]+=m;
        sh[i][0]=vl[i][0]+m;
        sh[i][1]=vl[i][1]+m;
        svl[i][0]=vl[i][0], svl[i][1]=vl[i][1], ssh[i][0]=sh[i][0], ssh[i][1]=sh[i][1];
        mp[vl[i][0]]=mp[vl[i][1]]=mp[sh[i][0]]=mp[sh[i][1]]=0;
    }
    for (auto &[x, y]:mp) y=++t;
    for (int i=1; i<=n ;i++) vl[i][0]=mp[vl[i][0]], vl[i][1]=mp[vl[i][1]], sh[i][0]=mp[sh[i][0]], sh[i][1]=mp[sh[i][1]];
    for (int i=1; i<=n; i++) s.update(1, 4*n, 1, vl[i][0], {vl[i][1], svl[i][1], i}), s.update(1, 4*n, 1, sh[i][0], {sh[i][1], ssh[i][1], i});
    for (int i=1; i<=n; i++)
    {
        auto [mx, sv, idx]=s.query(1, 4*n, 1, vl[i][0], vl[i][1]);
        auto tmp=svl[i][1];
        if (sv<=tmp) continue;
        pa[i][0]=idx;
        sm[i][0]=sv-tmp;
        //cout<<"pa "<<i<<' '<<pa[i][0]<<' '<<sm[i][0]<<'\n';
    }
    for (int j=1; j<kx; j++) for (int i=1; i<=n; i++) pa[i][j]=pa[pa[i][j-1]][j-1], sm[i][j]=sm[i][j-1]+sm[pa[i][j-1]][j-1];
    for (int i=1; i<=n; i++)
    {
        ll cur=svl[i][1]-svl[i][0], u=i, cnt=1;
        for (int j=kx-1; j>=0; j--) if (cur+sm[u][j]<m) cnt+=1<<j, cur+=sm[u][j], u=pa[u][j];
        //cout<<"cur "<<cur<<' '<<cnt<<' '<<u<<' '<<cur+sm[u][0]<<'\n';
        if (cur+sm[u][0]<m||u==0) continue;
        ans=min(ans, cnt+1);
    }
    if (ans==1e9) cout<<-1;
    else cout<<ans;
}

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