oj.uz

Submission #651597

# Submission time Handle Problem Language Result Execution time Memory
651597 2022-10-19T12:05:23 Z inksamurai Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 48644 KB 
#include <bits/stdc++.h>

// cut here
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
namespace atcoder {
 
namespace internal {
 
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
 
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
 
}  // namespace internal
 
}  // namespace atcoder
 
 
namespace atcoder {
 
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
 
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
 
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
 
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
 
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
 
    S all_prod() { return d[1]; }
 
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
 
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
 
  private:
    int _n, size, log;
    std::vector<S> d;
 
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
 
}  // namespace atcoder
// cut here 

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3CZAtRo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

const int inf=1e9;

// struct segtree{
// 	int n;
// 	vi seg;
// 	segtree(int _n=0){init(_n);}
// 	void init(int _n){
// 		n=_n;
// 		int si=1;
// 		while(si<=n) si*=2;
// 		si*=2;
// 		seg.clear();
// 		seg=vi(si,inf);
// 	}
// 	void set(int node,int l,int r,int pos,int x){
// 		if(l==r-1){
// 			seg[node]=x;
// 			return;
// 		}
// 		int m=(l+r)/2;
// 		if(pos<m){
// 			set(node*2+1,l,m,pos,x);
// 		}else{
// 			set(node*2+2,m,r,pos,x);
// 		}
// 		seg[node]=min(seg[node*2+1],seg[node*2+2]);
// 	}
// 	void set(int pos,int x){
// 		set(0,0,n,pos,x);
// 	}
// 	int prod(int node,int l,int r,int _l,int _r){
// 		if(l>=_r or r<=_l){
// 			// _e
// 			return inf;
// 		}
// 		if(_l<=l and r<=_r){
// 			return seg[node];
// 		}
// 		int m=(l+r)/2;
// 		return min(prod(node*2+1,l,m,_l,_r),prod(node*2+2,m,r,_l,_r));
// 	}
// 	int prod(int l,int r){
// 		return prod(0,0,n,l,r);
// 	}
// 	int get(int i){
// 		return prod(i,i+1);
// 	}
// };

int op(int l,int r){return min(l,r);}
int e(){return inf;}

struct dat{
	int l,r,id;
	dat(int _l=-1,int _r=-1,int _id=-1):
	l(_l),r(_r),id(_id){}
	bool operator<(const dat&a)const{
		return tuple<int,int,int>(a.r,a.l,a.id)<tuple<int,int,int>(r,l,id);
	}
};

signed main(){
_3CZAtRo;
	int n,q;
	cin>>n>>q;
	vec(dat) a(n);
	rep(i,n){
		cin>>a[i].l>>a[i].r;
		a[i].id=i;
	}
	vec(vec(pii)) qry(n);
	rep(_,q){
		int s,t;
		cin>>s>>t;
		qry[t-1].pb(pii(s-1,_));
	}
	vi tmp;
	rep(i,n){
		tmp.pb(a[i].l);
		tmp.pb(a[i].r);
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	int si=sz(tmp);
	rep(i,n){
		a[i].l=lower_bound(tmp.begin(),tmp.end(),a[i].l)-tmp.begin();
		a[i].r=lower_bound(tmp.begin(),tmp.end(),a[i].r)-tmp.begin();
	}	
	const int ln=17;
	vec(atcoder::segtree<int,op,e>) segs;
	rep(j,ln){
		atcoder::segtree<int,op,e> curseg(si);
		rep(i,n){
			curseg.set(i,inf);
		}
		segs.pb(curseg);
	}
	{
		rep(i,n){
			int l=a[i].l,r=a[i].r;
			int val=segs[0].get(r);
			segs[0].set(r,min(val,l));
		}
	}
	rng(j,1,ln){
		rep(i,n){
			int r=a[i].r;
			int l=segs[j-1].get(r);
			int val=segs[j-1].prod(l,r+1);
			int old_val=segs[j-1].get(r);
			segs[j].set(r,min(old_val,val));
		}
	}
	// print(" output points ");
	// for(auto p:a){
	// 	print(p.l,p.r);
	// }
	// print(".....");
	auto af=[&](int i,int need)->int{
		int res=1;
		int go=a[i].l;
		int r=a[i].r;
		// print(need,r);
		if(r<need) return inf;
		if(go<=need and need<=r) return 1;
		// print(segs[1].prod(go,r+1));
		// rep(_,4){
		// 	res+=1;
		// 	int ngo=segs[0].prod(go,r+1);
		// 	if(go<=need) break;
		// 	if(ngo==go) break;
		// 	go=ngo;
		// }
		// print(go);
		for(int j=ln-1;j>=0;j--){
			int ngo=go,pok=go<=need;
			for(int nj=j-1;nj>=0;nj--){
				int val=segs[nj].prod(ngo,r+1);
				if(val<=need)pok=1;
				ngo=val;
			}
			if(!pok){
				res+=1<<j;
				go=segs[j].prod(go,r+1);
			}
		}
		if(go>need) return inf;
		// print(go);
		return res;
	};
	// af(5,0);
	vi pns(q,inf);
	rep(i,n){
		for(auto p:qry[i]){
			if(p.fi==i){
				pns[p.se]=0;
			}else{
				pns[p.se]=af(i,a[p.fi].r);
			}
		}
	}
	rep(i,q){
		if(pns[i]==inf){
			cout<<"impossible\n";
		}else{
			cout<<pns[i]<<"\n";
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 840 ms 25184 KB Output is correct
3 Correct 862 ms 28684 KB Output is correct
4 Correct 1419 ms 29072 KB Output is correct
5 Correct 959 ms 28820 KB Output is correct
6 Correct 932 ms 28892 KB Output is correct
7 Correct 856 ms 29032 KB Output is correct
8 Correct 400 ms 48380 KB Output is correct
9 Correct 435 ms 48356 KB Output is correct
10 Correct 876 ms 29864 KB Output is correct
11 Correct 754 ms 48644 KB Output is correct
12 Correct 312 ms 28092 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Runtime error 1 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Runtime error 1 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Runtime error 1 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 25180 KB Output is correct
2 Correct 897 ms 28652 KB Output is correct
3 Execution timed out 1573 ms 28480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 840 ms 25184 KB Output is correct
3 Correct 862 ms 28684 KB Output is correct
4 Correct 1419 ms 29072 KB Output is correct
5 Correct 959 ms 28820 KB Output is correct
6 Correct 932 ms 28892 KB Output is correct
7 Correct 856 ms 29032 KB Output is correct
8 Correct 400 ms 48380 KB Output is correct
9 Correct 435 ms 48356 KB Output is correct
10 Correct 876 ms 29864 KB Output is correct
11 Correct 754 ms 48644 KB Output is correct
12 Correct 312 ms 28092 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Runtime error 1 ms 596 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -