oj.uz

답안 #853467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853467 2023-09-24T11:56:43 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 278 ms 95936 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii> 
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define ld long double
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)
const int MAXN = 1e5+5;
vvii table(MAXN,vpi(25,{0,0}));
struct Segment{
  int s,e,idx;
};

 
ii query(int l,int r){
 
  int len = r-l+1;
  int k = 31- __builtin_clz(len);
  return max(table[l][k], table[r-(1<<k)+1][k]);
}
 

bool cmp(Segment a, Segment b){
  if(a.s == b.s) return a.e <= b.e;
  return a.s < b.s;
}

bool cmp1(Segment a, Segment b){
  if(a.s == b.s) return a.e > b.e;
  return a.s < b.s;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,q; cin>>n>>q;
  vector<Segment> v(n);
  vpi start;
  For(i,n,0){
    int s,e; cin>>s>>e;
    v[i].s = s; v[i].e = e; v[i].idx = i;
    start.pb({s,i});
  }
  sort(all(v),cmp);
  vi idxs(n+1);
  vvi jump(n+1,vi(25,n));  
  For(i,n,0) table[i][0] = {v[i].e,i};
    For(k,25,1){
        for(int i = 0; i+ (1<<k) -1< n; i++){
            int x = i+(1<<(k-1));
            if(table[i][k-1].f == table[x][k-1].f) table[i][k] = min(table[i][k-1],table[x][k-1]);
            else table[i][k] = max(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    
    Segment S; S.s = v[i].e; S.e = 1e9; S.idx = 1e9;
    int idx = (upper_bound(all(v),S,cmp) - v.begin());
    idx--;
    //cerr<<i<<" "<<idx<<" "<<S.s<<" "<<S.e<<" "<<S.idx<<" "<<v[idx].s<<" "<<v[idx].e<<" "<<v[idx].idx<<endl;
    /*if(idx == i){
      jump[v[i].idx][0] = 0; continue;
    }*/
    ii p = query(0,idx);
    if(p.s == i || p.f == v[i].e) jump[i][0] = n; 
    else jump[i][0] = p.s;
  }
  //Build Binary Lifting
  For(k,25,1){
    For(i,n,0){
      jump[i][k] = jump[jump[i][k-1]][k-1];
      if(jump[i][k] == i || jump[i][k] == jump[i][k-1]) jump[i][k] = n;
    }
  }
  For(i,n,0) idxs[v[i].idx] = i;
  /*For(i,n,0){
    cerr<<i<<" "<<v[i].s<<" "<<v[i].e<<" "<<v[i].idx<<endl;
    cerr<<jump[i][0]<<" "<<jump[i][1]<<" "<<jump[i][2]<<endl<<endl;
  }*/
  while(q--){
    int s,e; cin>>s>>e; s--,e--;s = idxs[s]; e = idxs[e];
    if(s == e){
      cout<<0<<endl; continue;
    }
    //cerr<<s<<" "<<e<<" ";
    int ans = 0;
    for(int i = 24; i>=0; i--){
      if(jump[s][i] < e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
    //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<endl;
    if(max(e,s) >= n) cout<<"impossible"<<endl;
    else if(!(v[e].s <= v[s].e && v[s].e <= v[e].e)) cout<<"impossible"<<endl;
    else cout<<ans+1<<endl;
  }

}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 43504 KB Output is correct
2 Correct 221 ms 71360 KB Output is correct
3 Correct 229 ms 71360 KB Output is correct
4 Correct 236 ms 71356 KB Output is correct
5 Correct 229 ms 71424 KB Output is correct
6 Correct 228 ms 71360 KB Output is correct
7 Correct 238 ms 71416 KB Output is correct
8 Correct 220 ms 71952 KB Output is correct
9 Correct 219 ms 72008 KB Output is correct
10 Correct 254 ms 71648 KB Output is correct
11 Correct 267 ms 71872 KB Output is correct
12 Runtime error 75 ms 95936 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 43356 KB Output is correct
2 Correct 23 ms 43380 KB Output is correct
3 Correct 24 ms 43612 KB Output is correct
4 Correct 24 ms 43608 KB Output is correct
5 Incorrect 23 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 43356 KB Output is correct
2 Correct 23 ms 43380 KB Output is correct
3 Correct 24 ms 43612 KB Output is correct
4 Correct 24 ms 43608 KB Output is correct
5 Incorrect 23 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 43356 KB Output is correct
2 Correct 23 ms 43380 KB Output is correct
3 Correct 24 ms 43612 KB Output is correct
4 Correct 24 ms 43608 KB Output is correct
5 Incorrect 23 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 71360 KB Output is correct
2 Correct 224 ms 71360 KB Output is correct
3 Correct 253 ms 71360 KB Output is correct
4 Correct 225 ms 71872 KB Output is correct
5 Correct 278 ms 71872 KB Output is correct
6 Correct 278 ms 71616 KB Output is correct
7 Correct 266 ms 71616 KB Output is correct
8 Correct 260 ms 71612 KB Output is correct
9 Correct 94 ms 70848 KB Output is correct
10 Correct 237 ms 71352 KB Output is correct
11 Correct 222 ms 70924 KB Output is correct
12 Correct 229 ms 71616 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 43504 KB Output is correct
2 Correct 221 ms 71360 KB Output is correct
3 Correct 229 ms 71360 KB Output is correct
4 Correct 236 ms 71356 KB Output is correct
5 Correct 229 ms 71424 KB Output is correct
6 Correct 228 ms 71360 KB Output is correct
7 Correct 238 ms 71416 KB Output is correct
8 Correct 220 ms 71952 KB Output is correct
9 Correct 219 ms 72008 KB Output is correct
10 Correct 254 ms 71648 KB Output is correct
11 Correct 267 ms 71872 KB Output is correct
12 Runtime error 75 ms 95936 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -