#866283 (C++14) No.2292 Interval Union Find

• 問題: No.2292 Interval Union Find
• ユーザー: kotatsugame
• 提出日時: 2023-05-05 21:43:58
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 213 ms / 5,000 ms
• コード長: 1,638 bytes
• コンパイル時間: 841 ms
• コンパイル使用メモリ: 78,828 KB
• 実行使用メモリ: 12,928 KB
• 最終ジャッジ日時: 2024-11-23 06:42:30
• 合計ジャッジ時間: 10,075 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 44

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<iostream>
#include<map>
using namespace std;
int N,Q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>Q;
    map<int,int>S;
    for(;Q--;)
    {
        int op;cin>>op;
        if(op==1)
        {
            int L,R;cin>>L>>R;
            auto it=S.lower_bound(L);
            if(it!=S.begin())
            {
                it--;
                if(it->second>=L)
                {
                    L=it->first;
                    R=max(R,it->second);
                    it=S.erase(it);
                }
                else it++;
            }
            while(it!=S.end()&&it->first<=R)
            {
                R=max(R,it->second);
                it=S.erase(it);
            }
            S.insert(it,make_pair(L,R));
        }
        else if(op==2)
        {
            int L,R;cin>>L>>R;
            auto it=S.lower_bound(L);
            if(it!=S.begin())
            {
                it--;
                if(it->second>R)
                {
                    pair<int,int>p=*it;
                    it=S.erase(it);
                    it=S.insert(it,make_pair(p.first,L));
                    it++;
                    S.insert(it,make_pair(R,p.second));
                    continue;
                }
                if(it->second>L)
                {
                    pair<int,int>p=*it;
                    it=S.erase(it);
                    p.second=L;
                    it=S.insert(it,p);
                    it++;
                }
                else it++;
            }
            while(it!=S.end()&&it->first<=R)
            {
                pair<int,int>p=*it;
                it=S.erase(it);
                p.first=R;
                if(p.first<p.second)
                {
                    S.insert(it,p);
                    break;
                }
            }
        }
        else if(op==3)
        {
            int u,v;cin>>u>>v;
            if(u>v)swap(u,v);
            if(u==v)
            {
                cout<<"1\n";
                continue;
            }
            auto it=S.upper_bound(u);
            if(it!=S.begin())
            {
                it--;
                if(it->second>=v)cout<<"1\n";
                else cout<<"0\n";
            }
            else cout<<"0\n";
        }
        else
        {
            int u;cin>>u;
            auto it=S.upper_bound(u);
            int ans=1;
            if(it!=S.begin())
            {
                it--;
                if(it->second>=u)
                {
                    ans=it->second-it->first+1;
                }
            }
            cout<<ans<<"\n";
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX