oj.uz

Submission #720580

# Submission time Handle Problem Language Result Execution time Memory
720580 2023-04-08T14:12:53 Z Johann Inside information (BOI21_servers) C++14
10 / 100
 84 ms 5028 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvpii vector<vpii>

void dfs(vvpii & adj, int v, int t, int source, vvb & reachable) {
    reachable[source][v] = true;
    for (pii e : adj[v]) {
        if (e.second < t) dfs(adj, e.first, e.second, source, reachable);
    }
}

int lowerbound(vpii & borders, int l, int r, int d) {
    while (l < r) {
        int m = (l + r) / 2;
        if (borders[m].second >= d) r = m;
        else l = m+1;
    }
    return l;
}
int otherbound(vpii & borders, int l, int r, int d) {
    while (l < r) {
        int m = (l + r + 1) / 2;
        if (borders[m].first <= d) l = m;
        else r = m-1;
    }
    return l;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N, K;
    cin >> N >> K;
    vpii borders(N);
    for (int i = 0; i < N; ++i) borders[i] = { i , i };
    for (int t = 1; t < N + K; ++t) {
        string command;
        cin >> command;
        if (command == "S") {
            int a, b;
            cin >> a >> b;
            --a; --b;
            if ( b < a ) swap(a, b);
            borders[a].second = borders[b].second;
            borders[b].first = borders[a].first;
        } else if (command == "Q") {
            int a,d;
            cin >> a >> d;
            --a; --d;
            if (borders[a].first <= d && d <= borders[a].second) cout << "yes\n";
            else cout << "no\n";
        } else {
            int d;
            cin >> d;
            --d;
            int l = lowerbound(borders, 0, d, d);
            int r = otherbound(borders, d, N-1, d);
            int cnt = r - l + 1;
            cout << cnt << "\n";
        }
    }
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1484 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 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1548 KB Output is correct
2 Correct 77 ms 4936 KB Output is correct
3 Correct 79 ms 4940 KB Output is correct
4 Correct 64 ms 4924 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1548 KB Output is correct
2 Correct 77 ms 4936 KB Output is correct
3 Correct 79 ms 4940 KB Output is correct
4 Correct 64 ms 4924 KB Output is correct
5 Correct 30 ms 1540 KB Output is correct
6 Correct 84 ms 4520 KB Output is correct
7 Correct 77 ms 4688 KB Output is correct
8 Correct 71 ms 4044 KB Output is correct
9 Correct 72 ms 4044 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1568 KB Output is correct
2 Correct 68 ms 4992 KB Output is correct
3 Correct 78 ms 5028 KB Output is correct
4 Correct 63 ms 4876 KB Output is correct
5 Incorrect 29 ms 1576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1568 KB Output is correct
2 Correct 68 ms 4992 KB Output is correct
3 Correct 78 ms 5028 KB Output is correct
4 Correct 63 ms 4876 KB Output is correct
5 Incorrect 29 ms 1576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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