oj.uz

답안 #1033838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033838 2024-07-25T06:51:17 Z 변재우(#10974) Fire (BOI24_fire) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=200010;
int N, M, W, P, ans, I[20][2*Nmax];
vector<pair<int, int>> V, T;
vector<int> X;

int F(int l, int r) {
    int ret=0;
    for(int i=19; i>=0; i--) if(I[i][l]<r) ret+=1<<i, l=I[i][l];
    if(I[0][l]<r) return Nmax;
    return ret+1;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>P;
    for(int i=1; i<=N; i++) {
        int x, y; cin>>x>>y;
        if(x>y) T.push_back({x, y});
        else V.push_back({x, y});
        X.push_back(x), X.push_back(y);
    }
    N=V.size(), M=T.size();
    X.push_back(0), X.push_back(P);
    sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
    W=X.size();
    for(int i=0; i<N; i++) {
        V[i].first=lower_bound(X.begin(), X.end(), V[i].first)-X.begin()+1;
        V[i].second=lower_bound(X.begin(), X.end(), V[i].second)-X.begin()+1;
    }
    for(int i=0; i<M; i++) {
        T[i].first=lower_bound(X.begin(), X.end(), T[i].first)-X.begin()+1;
        T[i].second=lower_bound(X.begin(), X.end(), T[i].second)-X.begin()+1;
    }
    sort(V.begin(), V.end());
    for(int i=1, j=0, mx=i; i<=W; i++) {
        while(j<V.size() && V[j].first<=i) mx=max(mx, V[j++].second);
        I[0][i]=mx;
    }
    for(int i=1; i<20; i++) for(int j=1; j<=W; j++) I[i][j]=I[i-1][I[i-1][j]];
    ans=F(1, W);
    for(auto [r, l]:T) ans=min(ans, 1+F(l, r));
    if(ans>N) cout<<-1;
    else cout<<ans;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:40:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while(j<V.size() && V[j].first<=i) mx=max(mx, V[j++].second);
      |               ~^~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -