oj.uz

답안 #855141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855141 2023-09-30T10:03:48 Z Litusiano Event Hopping (BOI22_events) C++14
30 / 100
 237 ms 40356 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){
    int l = 0; int r = n+1;
    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){
      p = query(i+1,idx);
    }
    if(p.s != i) jump[i][0] = p.s;
    else jump[i][0] = n;
  }
  //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;
  }

}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 194 ms 39320 KB Output is correct
3 Correct 198 ms 39636 KB Output is correct
4 Correct 202 ms 39368 KB Output is correct
5 Correct 202 ms 39364 KB Output is correct
6 Correct 204 ms 39324 KB Output is correct
7 Correct 206 ms 39320 KB Output is correct
8 Correct 199 ms 40356 KB Output is correct
9 Correct 191 ms 39868 KB Output is correct
10 Correct 237 ms 39624 KB Output is correct
11 Correct 236 ms 39620 KB Output is correct
12 Correct 182 ms 39892 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 12 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23280 KB Output is correct
5 Correct 13 ms 23132 KB Output is correct
6 Incorrect 13 ms 23132 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 12 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23280 KB Output is correct
5 Correct 13 ms 23132 KB Output is correct
6 Incorrect 13 ms 23132 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 12 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23280 KB Output is correct
5 Correct 13 ms 23132 KB Output is correct
6 Incorrect 13 ms 23132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 39364 KB Output is correct
2 Correct 197 ms 39344 KB Output is correct
3 Correct 205 ms 39324 KB Output is correct
4 Correct 204 ms 39880 KB Output is correct
5 Correct 228 ms 39780 KB Output is correct
6 Correct 228 ms 39328 KB Output is correct
7 Correct 222 ms 39388 KB Output is correct
8 Correct 220 ms 39620 KB Output is correct
9 Correct 67 ms 38596 KB Output is correct
10 Correct 202 ms 39136 KB Output is correct
11 Correct 206 ms 39112 KB Output is correct
12 Correct 200 ms 39200 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 194 ms 39320 KB Output is correct
3 Correct 198 ms 39636 KB Output is correct
4 Correct 202 ms 39368 KB Output is correct
5 Correct 202 ms 39364 KB Output is correct
6 Correct 204 ms 39324 KB Output is correct
7 Correct 206 ms 39320 KB Output is correct
8 Correct 199 ms 40356 KB Output is correct
9 Correct 191 ms 39868 KB Output is correct
10 Correct 237 ms 39624 KB Output is correct
11 Correct 236 ms 39620 KB Output is correct
12 Correct 182 ms 39892 KB Output is correct
13 Correct 13 ms 23132 KB Output is correct
14 Correct 12 ms 23132 KB Output is correct
15 Correct 13 ms 23132 KB Output is correct
16 Correct 13 ms 23280 KB Output is correct
17 Correct 13 ms 23132 KB Output is correct
18 Incorrect 13 ms 23132 KB Output isn't correct
19 Halted 0 ms 0 KB -