oj.uz

답안 #853492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853492 2023-09-24T12:30:25 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 43460 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));
            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;
    }*/
    if(i >= idx) {
      jump[i][0] = n; continue;
    }
    ii p = query(i,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--;
    if(s == e){
      cout<<0<<endl; continue;
    }
    s = idxs[s]; e = idxs[e];
    //cerr<<s<<" "<<e<<" ";
    int ans = 0;
    for(int i = 24; i>=0; i--){
      if(jump[s][i] < e && v[jump[s][i]].e <= v[e].e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
    //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<" "<<v[e].s<<" "<<v[s].e<<" "<<v[e].e<<endl;
    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 13 ms 23128 KB Output is correct
2 Execution timed out 1552 ms 43140 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 12 ms 23128 KB Output is correct
3 Correct 30 ms 23128 KB Output is correct
4 Correct 30 ms 23596 KB Output is correct
5 Incorrect 29 ms 23128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 12 ms 23128 KB Output is correct
3 Correct 30 ms 23128 KB Output is correct
4 Correct 30 ms 23596 KB Output is correct
5 Incorrect 29 ms 23128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 12 ms 23128 KB Output is correct
3 Correct 30 ms 23128 KB Output is correct
4 Correct 30 ms 23596 KB Output is correct
5 Incorrect 29 ms 23128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1544 ms 43460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Execution timed out 1552 ms 43140 KB Time limit exceeded
3 Halted 0 ms 0 KB -