oj.uz

답안 #569277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
569277 2022-05-27T08:14:30 Z inksamurai 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 104 ms 25428 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 
#define int long long
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3z2QF2y 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...);}
// e

int op(int l,int r){return l+r;}
int e(){return 0;}

signed main(){
_3z2QF2y;
	int n,m,q;
	cin>>n>>m>>q;
	vi bel(q,-1);
	vec(vec(tuple<int,int,int>)) adqry(n+1);
	vec(vec(pii)) qry(n+1);
	rep(i,q){
		int t;
		cin>>t;
		if(t==1){
			int l,r,k;
			cin>>l>>r>>bel[i]>>k;
			adqry[l-1].emplace_back(i,k,1);
			if(r<n) adqry[r].emplace_back(i,k,-1);
		}else if(t==2){
			assert(0);
		}else{
			int j,c;
			cin>>j>>c;
			qry[j-1].emplace_back(c,i);
		}
	}
	vi pns(q);
	atcoder::segtree<int,op,e> seg(q);
	rep(i,n){
		for(auto &[j,k,t]:adqry[i]){
			if(t==1){
				seg.set(j,k);
			}else{
				seg.set(j,0);
			}
		}
		for(auto &[b,j]:qry[i]){
			int l=0,r=q-1;
			int c=-1;
			while(l<=r){
				int m=(l+r)>>1;
				if(seg.prod(0,m+1)>=b){
					c=m,r=m-1;
				}else{
					l=m+1;
				}
			}
			if(c!=-1 and c<=j){
				pns[j]=bel[c];
			}
		}
	}
	rep(i,q){
		if(bel[i]!=-1) continue;
		cout<<pns[i]<<"\n";
	}
//
	return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 7636 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 25428 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 8340 KB Output is correct
2 Correct 91 ms 8372 KB Output is correct
3 Correct 99 ms 10480 KB Output is correct
4 Correct 77 ms 8584 KB Output is correct
5 Correct 104 ms 9608 KB Output is correct
6 Correct 79 ms 10504 KB Output is correct
7 Correct 51 ms 5316 KB Output is correct
8 Correct 52 ms 4980 KB Output is correct
9 Correct 67 ms 9056 KB Output is correct
10 Correct 64 ms 8548 KB Output is correct
11 Correct 77 ms 10444 KB Output is correct
12 Correct 70 ms 10476 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -