oj.uz

Submission #1099638

# Submission time Handle Problem Language Result Execution time Memory
1099638 2024-10-11T22:01:59 Z inksamurai Passport (JOI23_passport) C++17
48 / 100
 970 ms 1048576 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 all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
#define _3M8yqhy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
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;

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

int e(){
	return inf;
}

void chmin(int&a,int b){
	a=min(a,b);
}

void slv(){
	int n;
	cin>>n;

	vec(pii) a(n);
	rep(i,n){
		cin>>a[i].fi>>a[i].se;
	}

	rep(i,n){
		a[i].fi-=1,a[i].se-=1;
	}

	vec(vi) vsl(n),vsr(n);
	vec(vec(vi)) vs(n,vec(vi)(n));
	rep(i,n){
		vsl[a[i].fi].pb(i);
		vsr[a[i].se].pb(i);
		vs[a[i].fi][a[i].se].pb(i);
	}

	vec(vi) dp(n,vi(n,inf));
	dp[0][n-1]=0;
	atcoder::segtree<int,op,e> seg(n);
	rep(i,n){
		seg.set(i,inf);
	}
	vec(atcoder::segtree<int,op,e>) seg_a,seg_b;
	rep(i,n){
		seg_a.pb(seg);
		seg_b.pb(seg);
	}

	auto push=[&](int l,int r,int val){
		for(auto pos:vs[l][r]){
			seg.set(pos,val);
		}
	};
	
	auto push_l=[&](int l,int r,int val){
		auto it=upper_bound(all(vsl[l]),r);
		if(it!=vsl[l].begin()){
			it=prev(it);
		}else{
			return;
		}
		seg_a[r].set(*it,val);
	};

	auto push_r=[&](int l,int r,int val){
		auto it=lower_bound(all(vsr[r]),l);
		if(it==vsr[r].end()){
			return;
		}
		seg_b[l].set(*it,val);
	};
	
	push(0,n-1,1);
	push_l(0,n-1,1);
	push_r(0,n-1,1);
	for(int len=n;len>=1;len--){
		rep(l,n-len+1){
			int r=l+len-1;
			// full
			{
				int val=seg.prod(l,r+1);
				chmin(dp[l][r],val);
			}
			// l
			{
				int val=seg_a[r].prod(l,r+1);
				chmin(dp[l][r],val);
			}
			// r
			{
				int val=seg_b[l].prod(l,r+1);
				chmin(dp[l][r],val);
			}
			push(l,r,dp[l][r]+1);
			push_l(l,r,dp[l][r]+1);
			push_r(l,r,dp[l][r]+1);
		}
	}

	int q;
	cin>>q;
	rep(_,q){
		int x;
		cin>>x;
		x-=1;
		print(dp[x][x]==inf?-1:dp[x][x]);
	}
}

signed main(){
_3M8yqhy;
	slv();
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Runtime error 438 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 9 ms 5084 KB Output is correct
12 Correct 9 ms 5352 KB Output is correct
13 Correct 9 ms 5316 KB Output is correct
14 Correct 9 ms 4956 KB Output is correct
15 Correct 10 ms 5212 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 9 ms 5084 KB Output is correct
12 Correct 9 ms 5352 KB Output is correct
13 Correct 9 ms 5316 KB Output is correct
14 Correct 9 ms 4956 KB Output is correct
15 Correct 10 ms 5212 KB Output is correct
16 Correct 811 ms 300632 KB Output is correct
17 Correct 835 ms 330068 KB Output is correct
18 Correct 824 ms 332920 KB Output is correct
19 Correct 795 ms 319312 KB Output is correct
20 Correct 807 ms 332964 KB Output is correct
21 Correct 836 ms 332756 KB Output is correct
22 Correct 592 ms 332628 KB Output is correct
23 Correct 779 ms 332884 KB Output is correct
24 Correct 788 ms 332940 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 444 KB Output is correct
11 Correct 9 ms 5084 KB Output is correct
12 Correct 9 ms 5352 KB Output is correct
13 Correct 9 ms 5316 KB Output is correct
14 Correct 9 ms 4956 KB Output is correct
15 Correct 10 ms 5212 KB Output is correct
16 Correct 811 ms 300632 KB Output is correct
17 Correct 835 ms 330068 KB Output is correct
18 Correct 824 ms 332920 KB Output is correct
19 Correct 795 ms 319312 KB Output is correct
20 Correct 807 ms 332964 KB Output is correct
21 Correct 836 ms 332756 KB Output is correct
22 Correct 592 ms 332628 KB Output is correct
23 Correct 779 ms 332884 KB Output is correct
24 Correct 788 ms 332940 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 854 ms 316672 KB Output is correct
28 Correct 826 ms 333040 KB Output is correct
29 Correct 970 ms 332828 KB Output is correct
30 Correct 854 ms 332880 KB Output is correct
31 Correct 742 ms 317264 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Runtime error 438 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -