結果

問題 No.2421 entersys?
ユーザー asaringoasaringo
提出日時 2023-08-12 17:58:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,404 ms / 3,000 ms
コード長 8,023 bytes
コンパイル時間 3,927 ms
コンパイル使用メモリ 256,968 KB
実行使用メモリ 85,128 KB
最終ジャッジ日時 2024-04-30 13:05:19
合計ジャッジ時間 24,514 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 5 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 4 ms
6,940 KB
testcase_06 AC 4 ms
6,940 KB
testcase_07 AC 4 ms
6,940 KB
testcase_08 AC 5 ms
6,940 KB
testcase_09 AC 6 ms
6,940 KB
testcase_10 AC 6 ms
6,944 KB
testcase_11 AC 1,050 ms
67,212 KB
testcase_12 AC 1,018 ms
67,352 KB
testcase_13 AC 1,023 ms
66,996 KB
testcase_14 AC 1,042 ms
66,832 KB
testcase_15 AC 1,058 ms
66,544 KB
testcase_16 AC 1,085 ms
70,184 KB
testcase_17 AC 1,063 ms
70,096 KB
testcase_18 AC 1,068 ms
70,452 KB
testcase_19 AC 1,055 ms
69,920 KB
testcase_20 AC 1,056 ms
69,948 KB
testcase_21 AC 926 ms
66,352 KB
testcase_22 AC 879 ms
64,004 KB
testcase_23 AC 1,400 ms
84,996 KB
testcase_24 AC 1,404 ms
84,912 KB
testcase_25 AC 1,399 ms
85,128 KB
testcase_26 AC 675 ms
63,532 KB
testcase_27 AC 678 ms
62,844 KB
testcase_28 AC 682 ms
64,132 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}

// 座標圧縮
template<typename T=int> struct Compress{
    private:
        vector<int> vec ; // 元の値の座標圧縮後の値
        unordered_map<T,int> mp ; // 元の値 -> 変換された値
        unordered_map<int,T> np ; // 変換された値 -> 元の値

        void build(vector<T> A){
            int n = A.size() ;
            vector<T> B(n) ;
            for(int i = 0 ; i < n ; i++) B[i] = A[i] ;
            vec.resize(n) ;
            sort(A.begin(),A.end()) ;
            for(int i = 0 ; i < n ; i++){
                auto it = lower_bound(A.begin(),A.end(),B[i]) ;
                int id = it - A.begin() ;
                vec[i] = id ;
                mp[B[i]] = id;
                np[id] = B[i] ;
            }
        }

    public:
        Compress(){}
        Compress(vector<T> A) { build(A); }
        size_t size() {return vec.size() ; }
        // 元の値 -> 変換された値
        inline int encrypt(T i) { return mp[i] ; }
        // 変換された値 -> 元の値
        inline T decrypt(int i) { return np[i] ; }
        vector<int> compress() { return vec; }
        vector<int> compress(vector<T> A) { build(A); return vec; }
        inline int operator [] (int i) { return vec[i] ; }
};

// function               : return              : description
// -----------------------------------------------------
// Compress()             : void          : コンストラクタ
// Compress(vector<ll> A) : void          : コンストラクタ, 座圧する
// encrypt(ll v)          : int           : 元の値 -> 座圧後の値
// decrypt(int v)         : ll            : 座圧後の値 -> 元の値
// compress()             : vector<int>   : 座圧後の値
// operator[i]            : int           : 座圧後の値の vector にアクセスすることが可能

template<typename T>
struct LazySegmentTree{
    private :
        const ll linf = 1e18 ;
        const int inf = 1e8 ;

        int n , n_ ;
        vector<T> dat , lazy ;

        void build(){
            n = 1 ;
            while(n < n_) n *= 2 ;
            dat.resize(2*n-1,0) ;
            lazy.resize(2*n-1,0) ;
        }

        // 遅延評価
        void eval(int k){
            dat[k] += lazy[k] ;
            if(k < n - 1){
                lazy[2 * k + 1] += lazy[k] / 2 ;
                lazy[2 * k + 2] += lazy[k] / 2 ;
            }
            lazy[k] = 0 ;
        }

        // 区間加算
        void add_(int a , int b , int k , int  l , int r , T w){
            eval(k) ;
            if(b <= l || r <= a) return ;
            if(a <= l && r <= b) {
                // 区間加算
                lazy[k] += (r - l) * w ;
                eval(k) ;
                return ;
            }
            add_(a,b,2*k+1,l,(l+r)/2,w) ;
            add_(a,b,2*k+2,(l+r)/2,r,w) ;
            // 区間の更新をする必要がある
            dat[k] = dat[2*k+1] + dat[2*k+2] ;
        }
        void add_(int a , int b , T x){
            return add_(a,b,0,0,n,x) ;
        }

        T query_(int a , int b , int k , int l , int r){
            //遅延評価（これは確実に必要）
            eval(k) ;
            if(b <= l || r <= a) return 0 ;
            if(a <= l && r <= b) return dat[k] ;
            T lef = query_(a,b,2*k+1,l,(l+r)/2) ;
            T rig = query_(a,b,2*k+2,(l+r)/2,r) ;
            return lef + rig ;
        }

        T query_(int a , int b){
            return query_(a,b,0,0,n)  ;
        }

    public :
        LazySegmentTree(int _n) : n_(_n) { build() ; }
        T query(int a , int b) { return query_(a,b) ; }
        void add(int a , int b , T x) { add_(a,b,x) ; }
};

int n;

void solve(){
    cin >> n;
    map<string,set<pair<int,int>>> mp;
    vector<ll> V;
    rep(i,n){
        string s;
        int l, r;
        cin >> s >> l >> r;
        V.push_back(l);
        V.push_back(r);
        mp[s].insert({l,r});
    }
    int q;
    cin >> q;
    vector<tuple<ll,ll,ll,ll,string>> Q(q);
    rep(i,q){
        int t;
        cin >> t;
        if(t == 1){
            string s;
            int x;
            cin >> s >> x;
            Q[i] = {i,t,x,-1,s};
            V.push_back(x);
        }
        if(t == 2){
            int x;
            cin >> x;
            Q[i] = {i,t,x,-1,""};
            V.push_back(x);
        }
        if(t == 3){
            string s;
            int l, r;
            cin >> s >> l >> r;
            Q[i] = {i,t,l,r,s};
            V.push_back(l);
            V.push_back(r);
        }
    }
    Compress<ll> C(V);
    LazySegmentTree<ll> segtree(C.size());
    for(auto [key,vec] : mp){
        for(auto[l,r]:vec){
            auto lv = C.encrypt(l);
            auto rv = C.encrypt(r);
            segtree.add(lv,rv+1,1);
        }
    }
    rep(i,q){
        auto[id,t,l,r,s] = Q[i];
        if(t == 1){
            auto x = l;
            auto it = mp[s].upper_bound({x,1e9});
            bool ok = false;
            if(it != mp[s].begin()){
                it--;
                ok = (x <= (*it).second);
            }
            if(ok) {pt("Yes")}
            else {pt("No")}
        }
        if(t == 2){
            auto x = l;
            auto xv = C.encrypt(x);
            pt(segtree.query(xv,xv+1))
        }
        if(t == 3){
            auto lv = C.encrypt(l);
            auto rv = C.encrypt(r);
            segtree.add(lv,rv+1,1);
            mp[s].insert({l,r});
        }
    }
}

int main(){
    fast_io
    int t = 1;
    // cin >> t;
    rep(i,t) solve();
}
0