oj.uz

답안 #855138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855138 2023-09-30T09:59:43 Z Litusiano Event Hopping (BOI22_events) C++17
30 / 100
 243 ms 42252 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 min(table[l][k], table[r-(1<<k)+1][k]);
}
 


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

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({e,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].s,i};
    For(k,25,1){
        for(int i = 0; i+ (1<<k) -1< n; i++){
            int x = i+(1<<(k-1));
            table[i][k] = min(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    Segment S; S.s = v[i].s; S.e = 1e9; S.idx = 1e9;
    int l = 0; int r = n;
    while(r > l+1){
      int m = (l+r)/2;
      if(v[m].e >= v[i].s) l = m;
      else r = m;
    }
    int idx = l;
    //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;
    }*/
    //cerr<<"IDX "<<idx<<" "<<i<<endl;
    if(i >= idx) {
      jump[i][0] = n; continue;
    }
    ii p = query(i,idx);
    //cerr<<"IDX "<<v[i].s<<" "<<v[i].e<<" "<<idx<<" "<<i<<" "<<p.f<<" "<<p.s<<endl;
    if(p.s == i){
      if(i != 0) p = query(i+1,idx);
    }
    if(p.s != i) 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--; swap(s,e);
    if(s == e){
      cout<<0<<endl; continue;
    }
    s = idxs[s]; e = idxs[e];
    //cerr<<s<<" "<<e<<endl;
    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<<" "<<v[e].s<<" "<<v[s].e<<" "<<v[e].e<<endl;
    if(!(v[e].e >= v[s].s && v[e].e <= v[s].e)) cout<<"impossible"<<endl;
    else cout<<ans+1<<endl;
  }

}

Compilation message

events.cpp: In function 'int main()':
events.cpp:64:13: warning: variable 'S' set but not used [-Wunused-but-set-variable]
   64 |     Segment S; S.s = v[i].s; S.e = 1e9; S.idx = 1e9;
      |             ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 195 ms 39332 KB Output is correct
3 Correct 199 ms 39320 KB Output is correct
4 Correct 215 ms 39404 KB Output is correct
5 Correct 208 ms 39332 KB Output is correct
6 Correct 205 ms 39280 KB Output is correct
7 Correct 209 ms 39400 KB Output is correct
8 Correct 193 ms 39740 KB Output is correct
9 Correct 193 ms 39680 KB Output is correct
10 Correct 243 ms 39580 KB Output is correct
11 Correct 223 ms 39656 KB Output is correct
12 Correct 184 ms 42252 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 13 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23332 KB Output is correct
6 Incorrect 14 ms 23328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 13 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23332 KB Output is correct
6 Incorrect 14 ms 23328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 13 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23332 KB Output is correct
6 Incorrect 14 ms 23328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 39356 KB Output is correct
2 Correct 204 ms 39332 KB Output is correct
3 Correct 205 ms 39280 KB Output is correct
4 Correct 194 ms 39880 KB Output is correct
5 Correct 223 ms 39632 KB Output is correct
6 Correct 218 ms 39504 KB Output is correct
7 Correct 221 ms 39320 KB Output is correct
8 Correct 214 ms 39568 KB Output is correct
9 Correct 66 ms 38600 KB Output is correct
10 Correct 195 ms 39112 KB Output is correct
11 Correct 198 ms 39428 KB Output is correct
12 Correct 198 ms 39108 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 195 ms 39332 KB Output is correct
3 Correct 199 ms 39320 KB Output is correct
4 Correct 215 ms 39404 KB Output is correct
5 Correct 208 ms 39332 KB Output is correct
6 Correct 205 ms 39280 KB Output is correct
7 Correct 209 ms 39400 KB Output is correct
8 Correct 193 ms 39740 KB Output is correct
9 Correct 193 ms 39680 KB Output is correct
10 Correct 243 ms 39580 KB Output is correct
11 Correct 223 ms 39656 KB Output is correct
12 Correct 184 ms 42252 KB Output is correct
13 Correct 13 ms 23132 KB Output is correct
14 Correct 13 ms 23132 KB Output is correct
15 Correct 13 ms 23132 KB Output is correct
16 Correct 13 ms 23132 KB Output is correct
17 Correct 13 ms 23332 KB Output is correct
18 Incorrect 14 ms 23328 KB Output isn't correct
19 Halted 0 ms 0 KB -