Submission #444419

#TimeUsernameProblemLanguageResultExecution timeMemory
444419yungyaoInside information (BOI21_servers)C++17
5 / 100
75 ms7748 KiB
using namespace std; #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <utility> #include <memory.h> #include <map> #include <set> typedef long long LL; typedef pair<int,int> pii; #define F first #define S second #define pb push_back #define mkp make_pair #define iter(x) x.begin(),x.end() const int maxn = 12e4 + 100; int n,k; set <int> st[maxn]; int cnt[maxn]; void brutesolve(){ for (int i=1;i<=n;++i) {st[i].insert(i); cnt[i] = 1;} for (int _=n+k-1;_--;){ char o; cin >> o; if (o == 'S'){ int u,v; cin >> u >> v; set <int> ele; for (auto i:st[u]) {ele.insert(i); ++cnt[i];} for (auto i:st[v]) {ele.insert(i); ++cnt[i];} st[u] = ele; st[v] = ele; } else if (o == 'Q'){ int a,b; cin >> a >> b; cout << (st[a].find(b) != st[a].end() ? "yes\n" : "no\n"); } else{ int c; cin >> c; cout << cnt[c] << '\n'; } } } int bit[maxn]; pii ans[maxn]; int query(int k){ int ret = 0; for (;k;k-=k&-k) ret += bit[k]; return ret; } void update(int k,int val){ for (;k<=n;k+=k&-k) bit[k] += val; } void solve(){ bit[1] = 1; for (int i=1;i<=n;++i) ans[i] = mkp(i,i); for (int _=n+k-1;_--;){ char o; cin >> o; if (o == 'S'){ int u,v; cin >> u >> v; if (u > v) swap(u,v); ans[u] = ans[v] = mkp(ans[u].F,ans[v].S); update(ans[u].F,1); update(ans[v].S + 2,-1); //cout << ans[u].F << ' ' << ans[v].S << '\n'; } else if (o == 'Q'){ int a,b; cin >> a >> b; cout << (b >= ans[a].F and b <= ans[a].S ? "yes\n" : "no\n"); } else{ int c; cin >> c; cout << query(c) << '\n'; } } //for (int i=1;i<=n;++i) cout << ans[i].F << ' ' << ans[i].S << '\n'; //for (int i=1;i<=n;++i) cout << query(i) << ' '; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k; //if (n <= 4000) brutesolve(); else solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...