oj.uz

Submission #1019598

# Submission time Handle Problem Language Result Execution time Memory
1019598 2024-07-11T04:45:55 Z 변재우(#10911) Event Hopping (BOI22_events) C++17
0 / 100
 144 ms 30812 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<<"0\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 4696 KB Output is correct
2 Correct 106 ms 28616 KB Output is correct
3 Correct 142 ms 28752 KB Output is correct
4 Correct 144 ms 28612 KB Output is correct
5 Incorrect 102 ms 29380 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 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 3 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 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 3 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 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 3 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 108 ms 28612 KB Output is correct
2 Correct 122 ms 28612 KB Output is correct
3 Correct 129 ms 28616 KB Output is correct
4 Correct 110 ms 30812 KB Output is correct
5 Correct 130 ms 29304 KB Output is correct
6 Incorrect 123 ms 30664 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 4696 KB Output is correct
2 Correct 106 ms 28616 KB Output is correct
3 Correct 142 ms 28752 KB Output is correct
4 Correct 144 ms 28612 KB Output is correct
5 Incorrect 102 ms 29380 KB Output isn't correct
6 Halted 0 ms 0 KB -