oj.uz

답안 #907448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907448 2024-01-15T15:37:51 Z Darren0724 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 63696 KB 
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
//#define endl '\n'
const int N=200005;
const int INF=1e9;
struct segtree{
    int v[N<<2];
    segtree(){
        memset(v,0x3f,sizeof(v));
    }
    void add(int id,int l,int r,int a,int b,int x){
        if(a<=l&&b>=r){v[id]=min(v[id],x); return;} 
        int m=(l+r)>>1;
        if(a<m)add(id<<1,l,m,a,b,x);
        if(b>m)add(id<<1|1,m,r,a,b,x);
        v[id]=min(v[id],v[id<<1]);
        v[id]=min(v[id],v[id<<1|1]);
    }
    int ask(int id,int l,int r,int a,int b){
        if(a<=l&&b>=r)return v[id];
        int ans=INF;
        int m=(l+r)>>1;
        if(a<m)ans=min(ans,ask(id<<1,l,m,a,b));
        if(b>m)ans=min(ans,ask(id<<1|1,m,r,a,b));
        return ans;
    }
};
int32_t main() {
    LCBorz;
    int n,q;cin>>n>>q;
    vector<int> a(n),b(n),a1(n),b1(n);
    vector<int> li;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        li.push_back(a[i]);
        li.push_back(b[i]);
    }
    sort(all(li));
    li.resize(unique(all(li))-li.begin());
    auto get=[&](int k)->int {
        return lower_bound(all(li),k)-li.begin();
    };
    for(int i=0;i<n;i++){
        a[i]=get(a[i]);
        b[i]=get(b[i]);
        a1[i]=a[i],b1[i]=b[i];
    }
    segtree st[18]{};
    for(int t=0;t<18;t++){
        for(int i=0;i<n;i++){
            st[t].add(1,0,N,b1[i],b1[i]+1,a1[i]);
        }
        for(int i=0;i<n;i++){
            a1[i]=st[t].ask(1,0,N,a1[i],b1[i]+1);
        }
    }
    for(int i=0;i<q;i++){
        int c,d;cin>>c>>d;
        c--;d--;
        if(c==d){cout<<0<<endl;continue;}
        int ans=0;
        int p=a[d];
        for(int t=17;t>=0;t--){
            int tmp=st[t].ask(1,0,N,p,b[d]+1);
            if(tmp>b[c]){
                ans+=1<<t;
                p=tmp;
            }
        }
        if(b[c]>b[d]||p<a[c]||a[c]>a[d]||ans==262143){
            cout<<"impossible"<<endl;
            continue;
        }
        cout<<ans+1+(p>b[c])<<endl;
    }
 
 
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 56656 KB Output is correct
2 Correct 1004 ms 62980 KB Output is correct
3 Correct 1033 ms 62996 KB Output is correct
4 Correct 1063 ms 63180 KB Output is correct
5 Correct 1010 ms 62904 KB Output is correct
6 Correct 1006 ms 62956 KB Output is correct
7 Correct 1000 ms 62888 KB Output is correct
8 Incorrect 817 ms 63696 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 56660 KB Output is correct
2 Correct 47 ms 56656 KB Output is correct
3 Correct 57 ms 56632 KB Output is correct
4 Correct 48 ms 56912 KB Output is correct
5 Correct 47 ms 56660 KB Output is correct
6 Incorrect 48 ms 56800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 56660 KB Output is correct
2 Correct 47 ms 56656 KB Output is correct
3 Correct 57 ms 56632 KB Output is correct
4 Correct 48 ms 56912 KB Output is correct
5 Correct 47 ms 56660 KB Output is correct
6 Incorrect 48 ms 56800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 56660 KB Output is correct
2 Correct 47 ms 56656 KB Output is correct
3 Correct 57 ms 56632 KB Output is correct
4 Correct 48 ms 56912 KB Output is correct
5 Correct 47 ms 56660 KB Output is correct
6 Incorrect 48 ms 56800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1008 ms 62824 KB Output is correct
2 Correct 1029 ms 62928 KB Output is correct
3 Correct 1076 ms 63244 KB Output is correct
4 Correct 814 ms 63416 KB Output is correct
5 Correct 1156 ms 63484 KB Output is correct
6 Execution timed out 1525 ms 62812 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 56656 KB Output is correct
2 Correct 1004 ms 62980 KB Output is correct
3 Correct 1033 ms 62996 KB Output is correct
4 Correct 1063 ms 63180 KB Output is correct
5 Correct 1010 ms 62904 KB Output is correct
6 Correct 1006 ms 62956 KB Output is correct
7 Correct 1000 ms 62888 KB Output is correct
8 Incorrect 817 ms 63696 KB Output isn't correct
9 Halted 0 ms 0 KB -