Submission #1141827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141827		hynmj	Fire (BOI24_fire)	C++20	0 / 100	0 ms	328 KiB

Main

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
template <typename T> using v = vector<T>;
const int INF = 1e18, MOD = 1e9+7, N = 2e5+7;
const int lg= 20;
ll sp[N][lg];
ll mxt[N][lg];
int m;
ll get(int l, int r)
{
    ll ch = 31 - __builtin_clz(r-l+1);
    return max(mxt[l][ch], mxt[r-(1ll<<ch)+1][ch]);
}
// Function to initialize the Sparse Table
int tilmx[N];
vector<pi> a;
bool app(int k, int binary)
{
    int l=k;
    for (int i = 0; i < lg; i++)
    {
        int mask = 1LL << i;
        if ((binary & mask) != 0)
        {
            k = sp[k][i];
        }
    }
    // cout <<k<<" "<<l<<endl;
    // cout << tilmx[k] << "  " <<a[l].ff<< endl;
    return get(l,k)-a[l].ff>=m;
}

void preprocess(int n)
{
    for (int p = 1; p < lg; p++)
    {
        for (int i = 1; i <= n; i++)
        {
            sp[i][p] = sp[sp[i][p - 1]][p - 1];
        }
    }
}

// Function to initialize the Sparse Table
void init(vector<pi>& ls)
{
    ll n = ls.size();
    for (int i=0; i<n; i++)
    {
        mxt[i][0] = ls[i].ss;
    }
    for (int i=1; i<lg; i++)
    {
        for (int j=0; j+(1ll<<i)<=n; j++)
        {
            mxt[j][i] = max(mxt[j][i-1], mxt[j+(1ll<<(i-1))][i-1]);
        }
    }
}

// Function to get the minimum value in the range [l, r]
void solve()
{
    int n, k, e,  ans = INF;
    cin >> n >> m;
    a.assign(n,{});

    rep(n)
    {
    	cin >> a[i].ff >> a[i].ss;
        if (a[i].ff>a[i].ss)a[i].ss+=m;
        
    }

    // cout <<a[0].ff<<endl;
    vi dp(n);    
    sort(all(a));
    int mn,mx;
    // n*=2;
    rep(n)
    {
        tilmx[i]=a[i].ss;
        if (i>0)
        tilmx[i]=max(tilmx[i-1],tilmx[i]);
        int op =1;
        mn=a[i].ff;
        mx=a[i].ss;
        int j=i+1;
        int k=0;
        set<int> ax;
        ax.insert(mx);
        int maxj = (--lower_bound(all(a),(pi){mx+1,-1}) - a.begin());
        sp[i][0]=maxj;
    }
    preprocess(n);
    init(a);
    rep(n)
    {
        int l=0,r=n+1;
        while (r-l>1)
        {
            int mid=(r+l)/2;
            if (app(i,mid))
            {
                r=mid;
            }
            else l=mid;
        }
        if(app(i,r))
        {
            // cout <<i<< " "<<r<<endl;
            ans=min(ans,r);
        }
    }
        // cout <<app(0,3)<<endl;





        
        
        

    






     cout << (ans==INF ? -1: ans+1);ln;
    // cout << a.size();
    // k=0;
    // for (auto i: a){cout << i.ff << " " <<i.ss<<" "<<sp[k][0]<<" "<<tilmx[k++];ln;}
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    rep(ans){
        // cout << "Case #" << i+1 << ": ";
        solve();ln;}}

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