oj.uz

답안 #853461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853461 2023-09-24T11:48:07 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 283 ms 95876 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+1});
  }
  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));
            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) 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 21 ms 43356 KB Output is correct
2 Correct 219 ms 71352 KB Output is correct
3 Correct 220 ms 71376 KB Output is correct
4 Correct 241 ms 71360 KB Output is correct
5 Correct 223 ms 71364 KB Output is correct
6 Correct 242 ms 71560 KB Output is correct
7 Correct 235 ms 71416 KB Output is correct
8 Correct 227 ms 72000 KB Output is correct
9 Correct 239 ms 71884 KB Output is correct
10 Correct 283 ms 72092 KB Output is correct
11 Correct 258 ms 71952 KB Output is correct
12 Runtime error 78 ms 95876 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 71308 KB Output is correct
2 Correct 229 ms 71472 KB Output is correct
3 Correct 236 ms 71484 KB Output is correct
4 Correct 221 ms 72172 KB Output is correct
5 Correct 268 ms 71812 KB Output is correct
6 Correct 270 ms 71652 KB Output is correct
7 Correct 267 ms 71616 KB Output is correct
8 Correct 245 ms 71788 KB Output is correct
9 Correct 88 ms 70852 KB Output is correct
10 Correct 219 ms 71296 KB Output is correct
11 Correct 216 ms 71000 KB Output is correct
12 Correct 230 ms 71468 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 43356 KB Output is correct
2 Correct 219 ms 71352 KB Output is correct
3 Correct 220 ms 71376 KB Output is correct
4 Correct 241 ms 71360 KB Output is correct
5 Correct 223 ms 71364 KB Output is correct
6 Correct 242 ms 71560 KB Output is correct
7 Correct 235 ms 71416 KB Output is correct
8 Correct 227 ms 72000 KB Output is correct
9 Correct 239 ms 71884 KB Output is correct
10 Correct 283 ms 72092 KB Output is correct
11 Correct 258 ms 71952 KB Output is correct
12 Runtime error 78 ms 95876 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -