답안 #759017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759017 2023-06-15T16:51:33 Z inksamurai 허수아비 (JOI14_scarecrows) C++17
15 / 100
4000 ms 26196 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 ll
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 _3p5IrEq 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...);}

#define all(a) a.begin(), a.end()

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

int e(){
	return 0;
}

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

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

	vi tmp;
	rep(i,n){
		tmp.pb(a[i].fi),tmp.pb(a[i].se);
	}
	sort(all(tmp));
	tmp.erase(unique(all(tmp)),tmp.end());
	const int si=sz(tmp);

	rep(i,n){
		a[i].fi=lower_bound(all(tmp),a[i].fi)-tmp.begin();
		a[i].se=lower_bound(all(tmp),a[i].se)-tmp.begin();
	}

	int ans=0;
	atcoder::segtree<int,op,e> seg(si);
	auto rec=[&](auto self,int l,int r,vec(pii) a)->void{
		if(l>=r-1){
			return;
		}
		int n=sz(a);
		int m=(l+r)/2;
		vec(pii) up,lo;
		rep(i,n){
			if(a[i].se>=m){
				up.pb(a[i]);
			}else{
				lo.pb(a[i]);
			}
		}
		sort(all(up)),reverse(all(up));
		sort(all(lo)),reverse(all(lo));
		set<pii> stup,stlo;
		int i=0,j=0;
		while(i<sz(up) or j<sz(lo)){
			int typ=0;
			if(j==sz(lo)){
				typ=1;
			}else if(i==sz(up)){
				typ=0;
			}else if(up[i].fi>lo[j].fi){
				typ=1;
			}
			if(typ){
				pii p=up[i];
				while(sz(stup)){
					auto it=prev(stup.end());
					pii q=*it;
					if(p.se<q.fi){
						seg.set(q.se,seg.get(q.se)-1);
						stup.erase(it);
					}else{
						break;
					}
				}
				seg.set(p.fi,seg.get(p.fi)+1);
				stup.insert({p.se,p.fi});
				i+=1;
			}else{
				int to=si;
				pii p=lo[j];
				for(auto q:stlo){
					if(q.se>p.se){
						to=min(to,q.fi);
					}
				}
				ans+=seg.prod(p.fi,to);
				stlo.insert(p);
				j+=1;
			}
		}
		for(auto p:up){
			seg.set(p.fi,0);
		}
		self(self,l,m,lo);
		self(self,m,r,up);
	};
	rec(rec,0,si,a);

	print(ans);
}

signed main(){
_3p5IrEq;
	slv();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 1672 KB Output is correct
2 Correct 57 ms 1536 KB Output is correct
3 Correct 42 ms 1616 KB Output is correct
4 Correct 35 ms 1384 KB Output is correct
5 Correct 39 ms 1412 KB Output is correct
6 Correct 47 ms 1536 KB Output is correct
7 Correct 51 ms 1484 KB Output is correct
8 Correct 37 ms 1880 KB Output is correct
9 Correct 50 ms 1552 KB Output is correct
10 Correct 47 ms 1488 KB Output is correct
11 Correct 50 ms 1508 KB Output is correct
12 Correct 23 ms 1580 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4038 ms 26196 KB Time limit exceeded
2 Halted 0 ms 0 KB -