제출 #1281447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281447		thanhcodedao	Fire (BOI24_fire)	C++20	0 / 100	198 ms	35668 KiB

Main

/****ThanhCodeDao*****/
/*******Azazel*******/
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 18
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
const ll maxN = 6e5+36, modd = 1e9+7;
struct Point {
    ll x,y;
};
ll cross(Point p,Point q,Point r) { // vi tri r voi duong pq >0 la ben trai, =0 la thang hang
    ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
ll dot(Point vecA,Point vecB) { // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc
    ll val = vecA.x*vecB.x + vecA.y*vecB.y;
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
double triarea(Point p,Point q,Point r) { // cross(pq * pr) / 2
    double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    return fabs(cross)/2.0;
}
/* de cho

*/
/* nhan xet nho

*/
/* nhan xet tu thuat trau
*/
int n,m;
pair<int,int> p[maxN];
bool cmp(pair<int,int> p1, pair<int,int> p2) {
    if(p1.F == p2.F) {
        return p1.S < p2.S;
    }
    return p1.F < p2.F;
}

    int ans = 1e9;
void dfs(int i,int finish,int &cnt,bool &isfinish) {
    int j = i;
    int mxr = 0, curchose = 0;
    while(j+1<=n and p[i].F <= p[j+1].F and p[j+1].F <= p[i].S+1) {
        if(p[j+1].S > mxr) {
            mxr = p[j+1].S;
            curchose = j+1;
        }
        ++j;
    }
    ++cnt;
    if(cnt >= ans) return ;
    if(i>n) return;
    if(mxr >= finish) {
        isfinish = true;
        return;
    } else {
        if(curchose == 0) {
            isfinish = false;
            return;
        }
        dfs(curchose,finish,cnt,isfinish);
    }
}
void sub3() {
    for(int i = 1; i<=n; i++) {
        bool isend = false;
        int cnt = 1;
        dfs(i,p[i].F + m,cnt,isend);
        if(isend) {
            ans = min(ans,cnt);
        }
    }
    if(ans == 1e9) ans = -1;
    cout << ans;
}
vector<int> compress;
struct node{
    int r,id;
    node operator + (const node & other){
        node res;
        res.r =max(r, other.r);
        if(r > other.r) {
            res.id = id;
        }else{
            res.id = other.id;
        }
        return res;
    }
} tree[maxN*4];
void up(int id,int l,int r,int idx,pair<int,int> val){
    if(idx < l || r < idx || l > r) return;
    if(l==r){
        tree[id].r = val.F;
        tree[id].id = val.S;
        return;
    }
    int mid = (l+r)/2;
    up(2*id,l,mid,idx,val);
    up(2*id+1,mid+1,r,idx,val);
    tree[id] = tree[id*2] + tree[id*2+1];
}
node get(int id,int l,int r,int u,int v){
    if(v < l || r < u || l > r) return {0,0};
    if(u<=l and r<=v) return tree[id];
    int mid = (l+r)/2;
    return get(2*id,l,mid,u,v) + get(2*id+1,mid+1,r,u,v);
}
int nxt[MLog+1][maxN];
int nhay(int start, int step){
    int u = start;
    for(int i = MLog;i>=0;i--){
        if(step >= bit(i) and u < n){
            u = nxt[i][u];
            step -= bit(i);
        }
    }
    return u;
}
int getmax(int i,int j,int finish){
    if(p[i].S >= finish) return i; // chi nhay 1 lan
    if(p[j].S >= finish) return j;
    if(p[i].S <= p[j].S) return j; // nhay xa hon
    return i;
}
void ac(){
    for(int i = 1;i<=n;i++){
        compress.pb(p[i].F);
        compress.pb(p[i].S);
        compress.pb(p[i].S+1);
//        cout << p[i].F << " " << p[i].S << '\n';
    }
//    cout << '\n' << '\n';
    sort(all(compress));
    uni(compress);
    int sz = compress.size() + 3;
    for(int i = n;i>=1;i--){
        int cl = lower_bound(all(compress),p[i].F) - compress.begin() + 1;
        int cr = lower_bound(all(compress),p[i].S+1) - compress.begin() + 1; // tim den r+1
        nxt[0][i] = get(1,1,sz,cl,cr).id;
        up(1,1,sz,cl, {p[i].S, i} );
    }
    nxt[0][n] = n;
    for(int i = 1;i<=MLog;i++){
        for(int j = 1;j<=n;j++){
            int finish = p[i].F + m;
            if(nxt[i-1][j] > n) continue;
//            if(i==1 and j == 1){
//                cout << nxt[i-1][j] << " " << nxt[i-1][nxt[i-1][j]] << '\n';
//                exit(0);
//            }
            nxt[i][j] = getmax(nxt[i-1][j], nxt[i-1][nxt[i-1][j]], finish);

        }
    }
    for(int i = 1;i<=n;i++){
//        cout << nxt[MLog][i] << ' ';
    }
    int ans = 1e9;
    for(int i = 1;i<=n;i++){
        int mxid = nxt[MLog][i];
        int  finish = p[i].F + m;
        if(p[mxid].S  < finish) continue; // toi da nhay dc -1

        int l = 0, r = n+10, res = 1e9;
        while(l<=r){
            int mid = (l+r)/2;
            int after = nhay(i, mid);
            if(p[after].S >= finish){
                res = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        ans = min(ans,res + 1);
    }
    if(ans == 1e9) ans = -1;
    cout << ans;
}
void solve() {
    cin >> n >> m;
    for(int i = 1; i<=n; i++) {
        cin >> p[i].F >> p[i].S;
        if(p[i].F > p[i].S) p[i].S += m;
    }
    sort(p+1,p+1+n,cmp);
//    if(n<=5000) {
//        sub3();
//        return;
//    }
    ac();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
//    freopen("inp.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    solve();
    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