結果

問題 No.2421 entersys?
ユーザー うえこうえこ
提出日時 2023-08-12 20:03:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,779 bytes
コンパイル時間 2,432 ms
コンパイル使用メモリ 191,100 KB
実行使用メモリ 22,372 KB
最終ジャッジ日時 2024-11-20 10:59:23
合計ジャッジ時間 12,652 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
void Compress(std::vector<int>& A)
{
    std::vector<int> B=A;//
    std::sort(B.begin(),B.end());
    B.erase(std::unique(B.begin(),B.end()),B.end());
    for(auto& a:A){
        a=static_cast<int>(std::lower_bound(B.begin(),B.end(),a)-B.begin());
    }
}
struct Query{
    int type;
    std::string s;
    int a,b;
};
//セグメント木はモノイドの二項演算
// +,*,^,&,|
//min,max
//gcd
//に対応可能
//^とgcdの単位元は0なので注意
using Type=int;

Type Op(Type l, Type r)
{
    return (l+r);
}

Type E() // モノイドの単位元
{
    return 0;
}

class SegTree
{
public:
    SegTree()=default;
    SegTree(size_t n)
    {
        //葉のサイズは2の累乗
        //nを十分格納できるサイズを求める
        while(m_size<n){
            m_size*=2;
        }
        m_nodes.resize(2*m_size-1,E());
    }
    
    void init(const std::vector<Type>& values){
        //葉ノードのセット
        for(size_t i=0;i<values.size();++i){
            m_nodes[m_size-1+i] = values[i];
        }
        //親の更新
        for(int i=static_cast<int>(m_size)-2;0<=i;--i){//size_tだと-1が大きな数に飛んでしまうのでintに直す
            update(i);
        }
    }
    
    //一点更新
    void set(size_t i,Type value)
    {
        size_t ni = m_size-1+i;
        m_nodes[ni]=value;
        while(0<ni)
        {
            ni=(ni-1)/2;
            update(ni);
        }
    }
    
    //一点取得
    Type get(size_t i)
    {
        size_t ni=m_size-1+i;
        return m_nodes[ni];
    }
    
    //区間クエリ
    //[begin,end)区間を調べる
        //↑イテレータの区間をよく思い出して
    Type query(size_t begin,size_t end)
    {
        //(調べたい区間,ni,ノードniが管理している区間)
        return query(begin,end,0,0,m_size);
    }
private:
    
    void update(size_t ni){
        m_nodes[ni]=Op(m_nodes[ni*2+1],m_nodes[ni*2+2]);
    }
    Type query(size_t begin,size_t end,size_t ni, size_t nBegin,size_t nEnd){
        //やることその1、調べたい区間が管理区間と無関係なら単位元を返す
        if(nEnd<=begin||end<=nBegin){
            return E();
        }
        //やることその２、管理区間が調べたい区間に収まっていれば
        if(begin<=nBegin&&nEnd<=end){
            return m_nodes[ni];
        }
        //やることその３、
        const Type lc = query(begin,end,ni*2+1,nBegin,(nBegin+nEnd)/2);
        const Type rc = query(begin,end,ni*2+2,(nBegin+nEnd)/2,nEnd);
        return Op(lc,rc);
    }
    size_t m_size = 1; //葉の数
    std::vector<Type> m_nodes;
    
};
int main(){
    int n;
    std::cin >> n;
    std::map<std::string,std::pair<int,int>>info;
    std::vector<int>room;
    for(int i=0;i<n;++i){
        std::string s;
        std::cin >> s;
        int a,b;
        std::cin >> a >> b;
        info[s]={a,b};
        room.push_back(a);
        room.push_back(b+1);
    }
    int q;
    std::cin >> q;
    std::vector<Query>query(q);
    for(int i=0;i<q;++i){
        std::cin >> query[i].type;
        if(query[i].type==1){
            std::cin >> query[i].s >> query[i].a;
        }
        else if(query[i].type==2){
            std::cin >> query[i].a;
        }
        else{
            std::cin >> query[i].s >> query[i].a >> query[i].b;
            room.push_back(query[i].a);
            room.push_back(query[i].b+1);
        }
    }
    std::vector<int>ori=room;
    std::sort(ori.begin(),ori.end());
    ori.erase(std::unique(ori.begin(),ori.end()),ori.end());
    Compress(room);
    std::vector<int>sum(room.size()+1);
    for(int i=0;i<n;++i){
        sum[room[2*i]]++;
        sum[room[2*i+1]]--;
    }
    //for(const auto&o:ori)std::cout << o << ' ' ;
    //std::cout << '\n';
    SegTree st(sum.size());
    st.init(sum);
    for(const auto&que:query){
        if(que.type==1){
            std::string x=que.s;
            int time=que.a;
            int lower=info[x].first,upper=info[x].second;
            if(lower<=time&&time<=upper){
                std::cout << "Yes\n";
            }
            else{
                std::cout << "No\n";
            }
        }
        else if(que.type==2){
            int time=que.a;
            int itr=std::lower_bound(ori.begin(), ori.end(), time)-ori.begin();
            std::cout << st.query(0,itr+1) << '\n';
        }
        else{
            std::string x=que.s;
            info[x]={que.a,que.b};
            int itr1=std::lower_bound(ori.begin(), ori.end(), que.a)-ori.begin();
            st.set(itr1, st.get(itr1)+1);
            int itr2=std::lower_bound(ori.begin(), ori.end(), que.b)-ori.begin();
            st.set(itr2, st.get(itr2)-1);
        }
    }
}
0