oj.uz

Submission #855154

# Submission time Handle Problem Language Result Execution time Memory
855154 2023-09-30T10:34:40 Z Litusiano Event Hopping (BOI22_events) C++17
30 / 100
 264 ms 40100 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);
  if(table[l][k].f == table[r-(1ll<<k)+1][k].f) return max(table[l][k], table[r-(1<<k)+1][k]);
  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));
            //if(k < 3) cerr<<"TABLE "<<i<<" "<<x<<" "<<k<<" "<<table[i][k-1].f<<" "<<table[i][k-1].s<<" "<<table[x][k-1].f<<" "<<table[x][k-1].s<<endl;
            if(table[i][k-1].f == table[x][k-1].f) table[i][k] = max(table[i][k-1],table[x][k-1]);
            else table[i][k] = min(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    int l = 0; int r = n;
    while(r > l+1){
      int m = (l+r)/2;
      //cerr<<v[m].e<<" "<<v[i].s<<endl;
      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(s == e){
      cout<<ans<<endl; continue;
    }
    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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23132 KB Output is correct
2 Correct 203 ms 39332 KB Output is correct
3 Correct 202 ms 39364 KB Output is correct
4 Correct 219 ms 39464 KB Output is correct
5 Correct 208 ms 39456 KB Output is correct
6 Correct 264 ms 39336 KB Output is correct
7 Correct 219 ms 39512 KB Output is correct
8 Correct 194 ms 39788 KB Output is correct
9 Correct 202 ms 39884 KB Output is correct
10 Correct 245 ms 39620 KB Output is correct
11 Correct 223 ms 39580 KB Output is correct
12 Correct 208 ms 39836 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 12 ms 23140 KB Output is correct
3 Correct 13 ms 23128 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23284 KB Output is correct
6 Incorrect 13 ms 23384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 12 ms 23140 KB Output is correct
3 Correct 13 ms 23128 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23284 KB Output is correct
6 Incorrect 13 ms 23384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 12 ms 23140 KB Output is correct
3 Correct 13 ms 23128 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23284 KB Output is correct
6 Incorrect 13 ms 23384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 39756 KB Output is correct
2 Correct 202 ms 39204 KB Output is correct
3 Correct 217 ms 39356 KB Output is correct
4 Correct 236 ms 40100 KB Output is correct
5 Correct 234 ms 39772 KB Output is correct
6 Correct 243 ms 39336 KB Output is correct
7 Correct 255 ms 39520 KB Output is correct
8 Correct 224 ms 39504 KB Output is correct
9 Correct 73 ms 38744 KB Output is correct
10 Correct 224 ms 39240 KB Output is correct
11 Correct 198 ms 38828 KB Output is correct
12 Correct 200 ms 39108 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23132 KB Output is correct
2 Correct 203 ms 39332 KB Output is correct
3 Correct 202 ms 39364 KB Output is correct
4 Correct 219 ms 39464 KB Output is correct
5 Correct 208 ms 39456 KB Output is correct
6 Correct 264 ms 39336 KB Output is correct
7 Correct 219 ms 39512 KB Output is correct
8 Correct 194 ms 39788 KB Output is correct
9 Correct 202 ms 39884 KB Output is correct
10 Correct 245 ms 39620 KB Output is correct
11 Correct 223 ms 39580 KB Output is correct
12 Correct 208 ms 39836 KB Output is correct
13 Correct 12 ms 23132 KB Output is correct
14 Correct 12 ms 23140 KB Output is correct
15 Correct 13 ms 23128 KB Output is correct
16 Correct 13 ms 23132 KB Output is correct
17 Correct 13 ms 23284 KB Output is correct
18 Incorrect 13 ms 23384 KB Output isn't correct
19 Halted 0 ms 0 KB -