oj.uz

Submission #1019600

# Submission time Handle Problem Language Result Execution time Memory
1019600 2024-07-11T04:47:01 Z 변재우(#10911) Event Hopping (BOI22_events) C++17
0 / 100
 144 ms 27592 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010, Nt=(1<<18);
int N, Q, S[Nmax], E[Nmax], L[20][Nmax];
vector<int> V;

class Seg {
public:
    Seg() {fill(Tree1+1, Tree1+2*Nt, Nt);}
    void Update(int k, int v1, int v2) {Update(1, 1, Nt, k, v1, v2);}
    int Query(int l, int r) {return Query(1, 1, Nt, l, r).second;}
private:
    int Tree1[2*Nt], Tree2[2*Nt];
    void Update(int node, int s, int e, int k, int v1, int v2) {
        if(s==e) {
            if(Tree1[node]>v1) Tree1[node]=v1, Tree2[node]=v2;
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v1, v2);
        else Update(rch, m+1, e, k, v1, v2);
        if(Tree1[lch]<Tree1[rch]) Tree1[node]=Tree1[lch], Tree2[node]=Tree2[lch];
        else Tree1[node]=Tree2[rch], Tree2[node]=Tree2[rch];
    }
    pair<int, int> Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return {Nt, 0};
        if(l<=s && e<=r) return {Tree1[node], Tree2[node]};
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        pair<int, int> a=Query(lch, s, m, l, r), b=Query(rch, m+1, e, l, r);
        if(a.first<b.first) return a;
        return b;
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>Q;
    for(int i=1; i<=N; i++) cin>>S[i]>>E[i], V.push_back(S[i]), V.push_back(E[i]);
    sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()), V.end());
    for(int i=1; i<=N; i++) {
        S[i]=lower_bound(V.begin(), V.end(), S[i])-V.begin()+1;
        E[i]=lower_bound(V.begin(), V.end(), E[i])-V.begin()+1;
        T.Update(E[i], S[i], i);
    }
    for(int i=1; i<=N; i++) L[0][i]=T.Query(S[i], E[i]);
    for(int i=1; i<20; i++) for(int j=1; j<=N; j++) L[i][j]=L[i-1][L[i-1][j]];
    while(Q--) {
        int ans=0;
        int s, e; cin>>s>>e;
        for(int i=19; i>=0; i--) if(S[L[i][e]]>E[s]) e=L[i][e], ans+=(1<<i);
        if(s==e) cout<<ans<<"\n";
        else {
            if(S[e]>E[s]) e=L[0][e], ans++;
            if(S[e]<=E[s] && E[s]<=E[e]) cout<<ans+1<<"\n";
            else cout<<"impossible\n";
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 107 ms 25512 KB Output is correct
3 Correct 125 ms 25560 KB Output is correct
4 Correct 142 ms 25496 KB Output is correct
5 Incorrect 104 ms 26216 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Incorrect 3 ms 4700 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Incorrect 3 ms 4700 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Incorrect 3 ms 4700 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 25556 KB Output is correct
2 Correct 144 ms 25608 KB Output is correct
3 Correct 134 ms 25540 KB Output is correct
4 Correct 117 ms 27588 KB Output is correct
5 Correct 118 ms 25800 KB Output is correct
6 Incorrect 115 ms 27592 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 107 ms 25512 KB Output is correct
3 Correct 125 ms 25560 KB Output is correct
4 Correct 142 ms 25496 KB Output is correct
5 Incorrect 104 ms 26216 KB Output isn't correct
6 Halted 0 ms 0 KB -