제출 #1281770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281770		TVSown	Fire (BOI24_fire)	C++20	100 / 100	189 ms	30940 KiB

Main

///*** Sown_Vipro ***///
/// ->TEAM SELECTION TEST<- ///

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
//#define int long long
const string NAME = "sown";
const int N = 2e6 + 5, MAX = 1e6, MOD = 1e9 + 7;
void maxi(int &x, int y){ if(x < y) x = y; }
void mini(int &x, int y){ if(x > y) x = y; };
void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); };
int n, m, M;
pi e[N], s[N];

int st[4 * N], p[30][N];

int Merge(int A, int B){
    if(s[A].S > s[B].S) return A;
    return B;
}

void update(int id, int l, int r, int i, int x){
    if(l > i || r < i) return;
    if(l == r){
        st[id] = Merge(st[id], x);
//        cout << st[id] << " " << x << "\n";
        return;
    }
    int m = (l + r) / 2;
    update(2 * id, l, m, i, x);
    update(2 * id + 1, m + 1, r, i, x);
    st[id] = Merge(st[2 * id], st[2 * id + 1]);
}

int get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(u <= l && r <= v) return st[id];
    int m = (l + r) / 2;

    return Merge(get(2 * id, l, m, u, v), get(2 * id + 1, m + 1, r, u, v));
}
vector<int> tmp;
void solve(){
    cin >> n >> M;
    tmp.pb(0);
    tmp.pb(M);
    FOR(i, 1, n){
        cin >> e[i].F >> e[i].S;
        tmp.pb(e[i].F);
        tmp.pb(e[i].S);
        if(e[i].F <= e[i].S){
            s[++m] = e[i];
        }else{
            s[++m] = {0, e[i].S};
            s[++m] = {e[i].F, M};
//            cout << e[i].F << " " << M <<C "\n";
        }
    }
    sort(s + 1, s + 1 + m);
    sort(all(tmp));
    tmp.erase(unique(all(tmp)), tmp.end());
//    cout << Merge(0, 1);
    REP(i, m, 1){
        int l = lower_bound(all(tmp), s[i].F) - tmp.begin() + 1;
        int r = lower_bound(all(tmp), s[i].S) - tmp.begin() + 1;
//        cout << s[i].F << " " << s[i].S << "\n";
        p[0][i] = get(1, 1, szz(tmp), l, r);
//        cout << i << " " << p[0][i] << "\n";
        update(1, 1, szz(tmp), l, i);
    }


    FOR(k, 1, 20) FOR(i, 1, m) p[k][i] = p[k - 1][p[k - 1][i]];

    e[n + 1] = {M, 0};
    int ans = 1e9;
    FOR(i, 1, n + 1){
        if(e[i].F <= e[i].S) continue;
        swap(e[i].F, e[i].S);
        int l = lower_bound(all(tmp), 0) - tmp.begin() + 1;
        int r = lower_bound(all(tmp), e[i].F) - tmp.begin() + 1;
//        cout << e[i].F + 1 << " " << l << " " << r << '\n';
        int u = get(1, 1, szz(tmp), l, r), res = (i != n + 1);
//        cout << u << "\n";
        REP(k, 20, 0){
            int v = p[k][u];
//            cout << k << " " << v << "\n";
            if(v && s[v].S < e[i].S){
                u = v;
                res += (1 << k);
            }
        }
        if(s[u].S >= e[i].S){
            ans = min(ans, res + 1);
        }
        if(s[p[0][u]].S >= e[i].S){
            ans = min(ans, res + 2);
        }
//        cout << res << " " << s[u].S << " " << s[p[0][u]].S << " " << e[i].S << "\n";
//        break;
    }
    if(ans == 1e9) cout << -1;
    else
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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