oj.uz

Submission #444418

# Submission time Handle Problem Language Result Execution time Memory
444418 2021-07-14T04:39:28 Z yungyao Inside information (BOI21_servers) C++17
0 / 100
 32 ms 6348 KB 
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;
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 6348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 6348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 6248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 6248 KB Output isn't correct
2 Halted 0 ms 0 KB -