oj.uz

답안 #855137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855137 2023-09-30T09:54:16 Z Litusiano Event Hopping (BOI22_events) C++14
20 / 100
 238 ms 42976 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;
    if(s > e){
      cout<<"impossible"<<endl; continue;
    }
    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(s == e){
      cout<<ans<<endl; continue;
    }
    if(!(v[e].e >= v[s].s)) 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 205 ms 40348 KB Output is correct
3 Correct 196 ms 39328 KB Output is correct
4 Correct 210 ms 39168 KB Output is correct
5 Correct 206 ms 39584 KB Output is correct
6 Correct 204 ms 42436 KB Output is correct
7 Correct 207 ms 42504 KB Output is correct
8 Correct 198 ms 42976 KB Output is correct
9 Correct 200 ms 42824 KB Output is correct
10 Correct 232 ms 42964 KB Output is correct
11 Incorrect 238 ms 42696 KB Output isn't correct
12 Halted 0 ms 0 KB -

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 14 ms 23132 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 15 ms 23128 KB Output is correct
6 Incorrect 14 ms 23088 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 14 ms 23132 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 15 ms 23128 KB Output is correct
6 Incorrect 14 ms 23088 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 14 ms 23132 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 15 ms 23128 KB Output is correct
6 Incorrect 14 ms 23088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 39368 KB Output is correct
2 Correct 201 ms 39240 KB Output is correct
3 Correct 210 ms 39472 KB Output is correct
4 Correct 200 ms 39876 KB Output is correct
5 Correct 225 ms 39624 KB Output is correct
6 Correct 218 ms 39364 KB Output is correct
7 Correct 213 ms 39368 KB Output is correct
8 Correct 207 ms 39448 KB Output is correct
9 Correct 66 ms 38604 KB Output is correct
10 Correct 198 ms 39156 KB Output is correct
11 Correct 195 ms 38888 KB Output is correct
12 Correct 208 ms 39156 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 205 ms 40348 KB Output is correct
3 Correct 196 ms 39328 KB Output is correct
4 Correct 210 ms 39168 KB Output is correct
5 Correct 206 ms 39584 KB Output is correct
6 Correct 204 ms 42436 KB Output is correct
7 Correct 207 ms 42504 KB Output is correct
8 Correct 198 ms 42976 KB Output is correct
9 Correct 200 ms 42824 KB Output is correct
10 Correct 232 ms 42964 KB Output is correct
11 Incorrect 238 ms 42696 KB Output isn't correct
12 Halted 0 ms 0 KB -