oj.uz

답안 #853464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853464 2023-09-24T11:54:39 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 298 ms 95940 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] != n && jump[s][i] < e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
   //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<endl;
    if(max(e,s) ==n || !(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 22 ms 43280 KB Output is correct
2 Correct 222 ms 71508 KB Output is correct
3 Correct 228 ms 71436 KB Output is correct
4 Correct 247 ms 71432 KB Output is correct
5 Correct 244 ms 71396 KB Output is correct
6 Correct 238 ms 71628 KB Output is correct
7 Correct 259 ms 71720 KB Output is correct
8 Correct 218 ms 71864 KB Output is correct
9 Correct 230 ms 71932 KB Output is correct
10 Correct 287 ms 71664 KB Output is correct
11 Correct 268 ms 71924 KB Output is correct
12 Runtime error 75 ms 95940 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 43412 KB Output is correct
2 Correct 23 ms 43608 KB Output is correct
3 Correct 23 ms 43756 KB Output is correct
4 Correct 23 ms 43716 KB Output is correct
5 Incorrect 23 ms 43644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 43412 KB Output is correct
2 Correct 23 ms 43608 KB Output is correct
3 Correct 23 ms 43756 KB Output is correct
4 Correct 23 ms 43716 KB Output is correct
5 Incorrect 23 ms 43644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 43412 KB Output is correct
2 Correct 23 ms 43608 KB Output is correct
3 Correct 23 ms 43756 KB Output is correct
4 Correct 23 ms 43716 KB Output is correct
5 Incorrect 23 ms 43644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 71360 KB Output is correct
2 Correct 233 ms 71652 KB Output is correct
3 Correct 286 ms 71496 KB Output is correct
4 Correct 221 ms 71872 KB Output is correct
5 Correct 289 ms 71868 KB Output is correct
6 Correct 298 ms 71704 KB Output is correct
7 Correct 279 ms 71576 KB Output is correct
8 Correct 261 ms 71672 KB Output is correct
9 Correct 97 ms 70932 KB Output is correct
10 Correct 221 ms 71100 KB Output is correct
11 Correct 220 ms 70904 KB Output is correct
12 Correct 234 ms 71408 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 43280 KB Output is correct
2 Correct 222 ms 71508 KB Output is correct
3 Correct 228 ms 71436 KB Output is correct
4 Correct 247 ms 71432 KB Output is correct
5 Correct 244 ms 71396 KB Output is correct
6 Correct 238 ms 71628 KB Output is correct
7 Correct 259 ms 71720 KB Output is correct
8 Correct 218 ms 71864 KB Output is correct
9 Correct 230 ms 71932 KB Output is correct
10 Correct 287 ms 71664 KB Output is correct
11 Correct 268 ms 71924 KB Output is correct
12 Runtime error 75 ms 95940 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -