제출 #1281422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281422		thanhcodedao	Fire (BOI24_fire)	C++20	40 / 100	2094 ms	1820 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 21
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
const ll maxN = 2e5+3, 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;
}
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;
//    }
//    cout << -1;
}

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: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26