oj.uz

Submission #444417

# Submission time Handle Problem Language Result Execution time Memory
444417 2021-07-14T04:38:58 Z yungyao Inside information (BOI21_servers) C++17
5 / 100
 2988 ms 382688 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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6348 KB Output is correct
2 Correct 48 ms 7612 KB Output is correct
3 Correct 287 ms 53100 KB Output is correct
4 Correct 42 ms 7236 KB Output is correct
5 Correct 41 ms 7096 KB Output is correct
6 Correct 2988 ms 382580 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6348 KB Output is correct
2 Correct 48 ms 7612 KB Output is correct
3 Correct 287 ms 53100 KB Output is correct
4 Correct 42 ms 7236 KB Output is correct
5 Correct 41 ms 7096 KB Output is correct
6 Correct 2988 ms 382580 KB Output is correct
7 Correct 29 ms 6312 KB Output is correct
8 Correct 45 ms 7524 KB Output is correct
9 Correct 331 ms 65276 KB Output is correct
10 Correct 37 ms 7236 KB Output is correct
11 Correct 39 ms 7044 KB Output is correct
12 Correct 2907 ms 382688 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6340 KB Output is correct
2 Incorrect 82 ms 8500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6340 KB Output is correct
2 Incorrect 82 ms 8500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6300 KB Output is correct
2 Incorrect 85 ms 7944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6300 KB Output is correct
2 Incorrect 85 ms 7944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6240 KB Output is correct
2 Incorrect 87 ms 8388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6240 KB Output is correct
2 Incorrect 87 ms 8388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6224 KB Output is correct
2 Incorrect 84 ms 8148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6224 KB Output is correct
2 Incorrect 84 ms 8148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6248 KB Output is correct
2 Correct 44 ms 7648 KB Output is correct
3 Correct 290 ms 53116 KB Output is correct
4 Correct 41 ms 7236 KB Output is correct
5 Correct 40 ms 7100 KB Output is correct
6 Correct 2961 ms 382564 KB Output is correct
7 Correct 29 ms 6340 KB Output is correct
8 Incorrect 83 ms 8520 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6248 KB Output is correct
2 Correct 44 ms 7648 KB Output is correct
3 Correct 290 ms 53116 KB Output is correct
4 Correct 41 ms 7236 KB Output is correct
5 Correct 40 ms 7100 KB Output is correct
6 Correct 2961 ms 382564 KB Output is correct
7 Correct 29 ms 6340 KB Output is correct
8 Incorrect 83 ms 8520 KB Output isn't correct
9 Halted 0 ms 0 KB -