結果

問題 No.2220 Range Insert & Point Mex
ユーザー hamathhamath
提出日時 2023-02-17 22:54:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 14,954 bytes
コンパイル時間 4,450 ms
コンパイル使用メモリ 262,240 KB
実行使用メモリ 94,224 KB
最終ジャッジ日時 2023-09-28 18:13:05
合計ジャッジ時間 14,284 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
11,296 KB
testcase_01 AC 51 ms
11,256 KB
testcase_02 AC 58 ms
11,388 KB
testcase_03 AC 60 ms
11,248 KB
testcase_04 AC 55 ms
11,356 KB
testcase_05 AC 60 ms
11,224 KB
testcase_06 AC 60 ms
11,292 KB
testcase_07 AC 58 ms
11,236 KB
testcase_08 AC 60 ms
11,248 KB
testcase_09 AC 60 ms
11,384 KB
testcase_10 AC 60 ms
11,392 KB
testcase_11 AC 56 ms
11,240 KB
testcase_12 AC 61 ms
11,452 KB
testcase_13 AC 259 ms
85,436 KB
testcase_14 AC 260 ms
85,156 KB
testcase_15 AC 261 ms
85,208 KB
testcase_16 AC 259 ms
84,436 KB
testcase_17 AC 262 ms
84,500 KB
testcase_18 AC 253 ms
84,020 KB
testcase_19 AC 254 ms
84,468 KB
testcase_20 AC 316 ms
94,224 KB
testcase_21 AC 315 ms
93,608 KB
testcase_22 AC 307 ms
93,144 KB
testcase_23 AC 272 ms
34,800 KB
testcase_24 AC 241 ms
33,576 KB
testcase_25 AC 209 ms
31,932 KB
testcase_26 AC 207 ms
34,536 KB
testcase_27 AC 112 ms
15,632 KB
testcase_28 AC 128 ms
29,836 KB
testcase_29 AC 129 ms
29,560 KB
testcase_30 AC 131 ms
29,504 KB
testcase_31 AC 173 ms
33,752 KB
testcase_32 AC 157 ms
31,692 KB
testcase_33 AC 223 ms
31,760 KB
testcase_34 AC 260 ms
53,952 KB
testcase_35 AC 332 ms
53,276 KB
testcase_36 AC 245 ms
36,960 KB
testcase_37 AC 316 ms
37,004 KB
testcase_38 AC 307 ms
53,496 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#else
    #pragma GCC optimize("O3")
    #pragma GCC optimize("unroll-loops")
    //#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#endif

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<char> Vc;
typedef vector<P> VP;
typedef vector<VP> VVP;
typedef vector<Vec> VV;
typedef vector<Vi> VVi;
typedef vector<Vc> VVc;
typedef vector<VV> VVV;
typedef vector<VVV> VVVV;
#define MAKEVV(variable, a, ...) VV variable(a, Vec(__VA_ARGS__))
#define MAKEVVc(variable, a, ...) VVc variable(a,Vc(__VA_ARGS__))
#define MAKEVVV(variable, a, b, ...) VVV variable(a, VV(b, Vec(__VA_ARGS__)))
#define MAKEVVVV(variable, a, b, c, ...) VVVV variable(a, VVV(b, (VV(c, Vec(__VA_ARGS__)))))

#define endl '\n'
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF = 4'000'000'000'000'000'010LL;
const ll MOD=998244353;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i)
#define SUM(a) accumulate(ALL(a),0LL)
#ifdef LOCAL
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgset(st) cerr << #st << ":"<<endl; for (auto i = st.begin(); i != st.end(); ++i) { cerr << *i <<" ";}cerr<<endl;
#define dbgarr(n,m,arr) rep(iii,n){rep(jjj,m){cerr<<arr[iii][jjj]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(iii,n){cerr<<arr[iii]<<" ";}cerr<<endl;
#else
#define dbg(...)
#define dbgmap(...)
#define dbgset(...)
#define dbgarr(...)
#define dbgdp(...)
#endif
#define out(a) cout<<a<<endl
#define outminusone(a) cout<< ( a==INF ? -1 : a ) <<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>auto lb(T &X, ll x){return lower_bound(ALL(X),x) - X.begin();}
template<class T>auto ub(T &X, ll x){return upper_bound(ALL(X),x) - X.begin();}
ll popcnt(ll x){return __builtin_popcount(x);}
ll topbit(ll t){return t==0?-1:63-__builtin_clzll(t);}
ll floor(ll y,ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return (y-x+1)/x;}return y/x;};
ll ceil(ll y, ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return y/x;}return (y+x-1)/x;};

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<typename T1, typename T2>
istream &operator>>(istream &i, pair<T1, T2> &p) { return i>>p.first>>p.second; }

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    s<<endl;
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

template<typename T=ll>
struct Zip {
    bool initialized;
    vector<T> v;
    Zip() : initialized(false) {}
    void add(T x) { v.push_back(x); }

    void init() {
        sort(ALL(v));
        Uniq(v);
        initialized = true;
    }

    ll id(T x) {
        if(!initialized) init();
        return lb(v, x);
    }

    T operator[](ll i) {
        if(!initialized) init();
        return v[i];
    }

    ll size() {
        if(!initialized) init();
        return v.size();
    }
};


struct AngelBeats {
    using i64 = long long;
    static constexpr i64 INF = numeric_limits<i64>::max() / 2.1;

    struct alignas(32) Node {
        i64 sum = 0, g1 = 0, l1 = 0;
        i64 g2 = -INF, gc = 1, l2 = INF, lc = 1, add = 0;
    };

    vector<Node> v;
    i64 n, log;

    AngelBeats() {}
    AngelBeats(int _n) : AngelBeats(vector<i64>(_n)) {}
    AngelBeats(const vector<i64>& vc) {
        n = 1, log = 0;
        while (n < (int)vc.size()) n <<= 1, log++;
        v.resize(2 * n);
        for (i64 i = 0; i < (int)vc.size(); ++i) {
            v[i + n].sum = v[i + n].g1 = v[i + n].l1 = vc[i];
        }
        for (i64 i = n - 1; i; --i) update(i);
    }

    void range_chmin(int l, int r, i64 x) { inner_apply<1>(l, r, x); }
    void range_chmax(int l, int r, i64 x) { inner_apply<2>(l, r, x); }
    void range_add(int l, int r, i64 x) { inner_apply<3>(l, r, x); }
    void range_update(int l, int r, i64 x) { inner_apply<4>(l, r, x); }
    i64 range_min(int l, int r) { return inner_fold<1>(l, r); }
    i64 range_max(int l, int r) { return inner_fold<2>(l, r); }
    i64 range_sum(int l, int r) { return inner_fold<3>(l, r); }

    void debug(ll n) {
        #ifdef LOCAL
        Vec res(n);
        rep(i, n)res[i] = range_sum(i, i+1);
        dbg(res);
        #endif
    }

private:
    void update(int k) {
        Node& p = v[k];
        Node& l = v[k * 2 + 0];
        Node& r = v[k * 2 + 1];

        p.sum = l.sum + r.sum;

        if (l.g1 == r.g1) {
            p.g1 = l.g1;
            p.g2 = max(l.g2, r.g2);
            p.gc = l.gc + r.gc;
        } else {
            bool f = l.g1 > r.g1;
            p.g1 = f ? l.g1 : r.g1;
            p.gc = f ? l.gc : r.gc;
            p.g2 = max(f ? r.g1 : l.g1, f ? l.g2 : r.g2);
        }

        if (l.l1 == r.l1) {
            p.l1 = l.l1;
            p.l2 = min(l.l2, r.l2);
            p.lc = l.lc + r.lc;
        } else {
            bool f = l.l1 < r.l1;
            p.l1 = f ? l.l1 : r.l1;
            p.lc = f ? l.lc : r.lc;
            p.l2 = min(f ? r.l1 : l.l1, f ? l.l2 : r.l2);
        }
    }

    void push_add(int k, i64 x) {
        Node& p = v[k];
        p.sum += x << (log + __builtin_clz(k) - 31);
        p.g1 += x;
        p.l1 += x;
        if (p.g2 != -INF) p.g2 += x;
        if (p.l2 != INF) p.l2 += x;
        p.add += x;
    }
    void push_min(int k, i64 x) {
        Node& p = v[k];
        p.sum += (x - p.g1) * p.gc;
        if (p.l1 == p.g1) p.l1 = x;
        if (p.l2 == p.g1) p.l2 = x;
        p.g1 = x;
    }
    void push_max(int k, i64 x) {
        Node& p = v[k];
        p.sum += (x - p.l1) * p.lc;
        if (p.g1 == p.l1) p.g1 = x;
        if (p.g2 == p.l1) p.g2 = x;
        p.l1 = x;
    }
    void push(int k) {
        Node& p = v[k];
        if (p.add != 0) {
            push_add(k * 2 + 0, p.add);
            push_add(k * 2 + 1, p.add);
            p.add = 0;
        }
        if (p.g1 < v[k * 2 + 0].g1) push_min(k * 2 + 0, p.g1);
        if (p.l1 > v[k * 2 + 0].l1) push_max(k * 2 + 0, p.l1);

        if (p.g1 < v[k * 2 + 1].g1) push_min(k * 2 + 1, p.g1);
        if (p.l1 > v[k * 2 + 1].l1) push_max(k * 2 + 1, p.l1);
    }

    void subtree_chmin(int k, i64 x) {
        if (v[k].g1 <= x) return;
        if (v[k].g2 < x) {
            push_min(k, x);
            return;
        }
        push(k);
        subtree_chmin(k * 2 + 0, x);
        subtree_chmin(k * 2 + 1, x);
        update(k);
    }

    void subtree_chmax(int k, i64 x) {
        if (x <= v[k].l1) return;
        if (x < v[k].l2) {
            push_max(k, x);
            return;
        }
        push(k);
        subtree_chmax(k * 2 + 0, x);
        subtree_chmax(k * 2 + 1, x);
        update(k);
    }

    template <int cmd>
    inline void _apply(int k, i64 x) {
        if constexpr (cmd == 1) subtree_chmin(k, x);
        if constexpr (cmd == 2) subtree_chmax(k, x);
        if constexpr (cmd == 3) push_add(k, x);
        if constexpr (cmd == 4) subtree_chmin(k, x), subtree_chmax(k, x);
    }

    template <int cmd>
    void inner_apply(int l, int r, i64 x) {
        if (l == r) return;
        l += n, r += n;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) _apply<cmd>(l++, x);
                if (r & 1) _apply<cmd>(--r, x);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <int cmd>
    inline i64 e() {
        if constexpr (cmd == 1) return INF;
        if constexpr (cmd == 2) return -INF;
        return 0;
    }

    template <int cmd>
    inline void op(i64& a, const Node& b) {
        if constexpr (cmd == 1) a = min(a, b.l1);
        if constexpr (cmd == 2) a = max(a, b.g1);
        if constexpr (cmd == 3) a += b.sum;
    }

    template <int cmd>
    i64 inner_fold(int l, int r) {
        if (l == r) return e<cmd>();
        l += n, r += n;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        i64 lx = e<cmd>(), rx = e<cmd>();
        while (l < r) {
            if (l & 1) op<cmd>(lx, v[l++]);
            if (r & 1) op<cmd>(rx, v[--r]);
            l >>= 1;
            r >>= 1;
        }
        if constexpr (cmd == 1) lx = min(lx, rx);
        if constexpr (cmd == 2) lx = max(lx, rx);
        if constexpr (cmd == 3) lx += rx;
        return lx;
    }
};

// [L,R)の範囲を管理
template<typename T>
struct RangeSet{
    set<pair<T,T>> st;
    T TINF;

    RangeSet(){
        TINF=numeric_limits<T>::max()/2;
        st.emplace(TINF,TINF);
        st.emplace(-TINF,-TINF);
    }
    // [l,r) covered?
    bool covered(T l,T r){
        r--;
        assert(l<=r);
        auto ite=prev(st.lower_bound({l+1,l+1}));
        return ite->first<=l and r<=ite->second;
    }
    bool covered(T x){
        return covered(x,x);
    }
    // [l, r)がカバーされているなら，その区間を返す. されていないなら[-TINF,-TINF]を返す
    pair<T,T> covered_by(T l,T r){
        r--;
        assert(l<=r);
        auto ite=prev(st.lower_bound({l+1,l+1}));
        if(ite->first<=l and r<=ite->second) return *ite;
        return make_pair(-TINF,-TINF);
    }
    pair<T,T> covered_by(T x){
        return covered_by(x,x);
    }
    // insert[l,r), 増加量を返す
    T insert(T l,T r){
        r--;
        assert(l<=r);
        auto ite=prev(st.lower_bound({l+1,l+1}));
        if(ite->first<=l and r<=ite->second) return T(0);
        T sum_erased=T(0);
        if(ite->first<=l and l<=ite->second+1){
            l=ite->first;
            sum_erased+=ite->second-ite->first+1;
            ite=st.erase(ite);
        }else ite=next(ite);
        while(r>ite->second){
            sum_erased+=ite->second-ite->first+1;
            ite=st.erase(ite);
        }
        if(ite->first-1<=r and r<=ite->second){
            sum_erased+=ite->second-ite->first+1;
            r=ite->second;
            st.erase(ite);
        }
        st.emplace(l,r);
        return r-l+1-sum_erased;
    }
//    T insert(T x){
//        return insert(x,x);
//    }
    // erase [l,r), 減少量を返す
    T erase(T l,T r){
        r--;
        assert(l<=r);
        auto ite=prev(st.lower_bound({l+1,l+1}));
        if(ite->first<=l and r<=ite->second){
            // 完全に1つの区間に包含されている
            if(ite->first<l)  st.emplace(ite->first,l-1);
            if(r<ite->second) st.emplace(r+1,ite->second);
            st.erase(ite);
            return r-l+1;
        }

        T ret=T(0);
        if(ite->first<=l and l<=ite->second){
            ret+=ite->second-l+1;// 消えた
            if(ite->first<l) st.emplace(ite->first,l-1);
            ite=st.erase(ite);// 次へ
        }else ite=next(ite);
        while(ite->second<=r){
            ret+=ite->second-ite->first+1;
            ite=st.erase(ite);
        }
        // 右端が区間の間にあるか
        if(ite->first<=r and r<=ite->second){
            ret+=r-ite->first+1;
            if(r<ite->second) st.emplace(r+1,ite->second);
            st.erase(ite);
        }
        return ret;
    }
//    T erase(T x){
//        return erase(x,x);
//    }
    // number of range
    int size(){
        return (int)st.size()-2;
    }
    // mex [x,~)
    T mex(T x=0){
        auto ite=prev(st.lower_bound({x+1,x+1}));
        if(ite->first<=x and x<=ite->second) return ite->second+1;
        else return x;
    }
    void output(){
        cout<<"RangeSet : ";
        for(auto &p:st){
            if(p.first==-TINF or p.second==TINF) continue;
            cout<<"["<<p.first<<", "<<p.second<<"] ";
        }
        cout<<"\n";
    }
    set<P> get(){
        set<P> res;
        Each(s, st){
            if(s.first==-TINF or s.second==TINF) continue;
            res.insert(mp(s.fi, s.se+1));
        }
        return res;
    }
};

int solve(){
    ll n;
    cin>>n;
    //vector<pair<ll,P>> query(n+1);
    map<ll,VP> query;
    Zip<ll> zip;
    rep(i, n){
        ll l,r,a;
        cin>>l>>r>>a;
        l--;
        zip.add(l);
        zip.add(r);
        //query[i] = mp(a,mp(l,r));
        query[a].emplace_back(l,r);
    }
    //sort(ALL(query));
    //dbg(query)

    ll Q;
    cin>>Q;
    Vec ques(Q);
    cin>>ques;
    rep(i,Q)ques[i]--;
    rep(i,Q)zip.add(ques[i]);
    zip.init();

    dbgmap(query);

    ll m = zip.size();
    dbg(m);
    dbg(zip.v);
    Vec init(m+2,INF/400);
    AngelBeats seg(init);
    ll mx = 1e5+10;
    //debug
    REP(x,0,mx){
        RangeSet<ll> rs;
        rs.insert(0,m);
        Each(p, query[x]){
            auto [l, r] = p;
            ll li = zip.id(l);
            ll ri = zip.id(r);
            dbg(-x)
            dbg(mp(li,ri))
            rs.erase(li,ri);
        }
        //dbg(x);
        Each(p, rs.get()){
            auto [l, r] = p;
            seg.range_chmin(l,r,x);
        }
        //seg.debug(m);
    }
    rep(i,Q){
        ll id = zip.id(ques[i]);
        ll ans = seg.range_sum(id,id+1);
        out(ans);
    }
    return  0;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(20);
//    ll T;
//    cin>>T;
//    while(T--)
    solve();
}
0