Submission #1224635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224635		SpyrosAliv	Inside information (BOI21_servers)	C++20	0 / 100	115 ms	4496 KiB

servers

#include <bits/stdc++.h>
using namespace std;

const int MN = 120005;
const int MQ = 120005;
int n, q;
vector<vector<int>> tree(MN);
vector<int> par(MN, 0), idx(MN, 0);

class segTree {
    vector<int> seg;
    int n;
    int query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        else if (start >= l && end <= r) return seg[node];
        else {
            int mid = (start + end) / 2;
            return query(node*2, start, mid, l, r) + query(node*2+1, mid+1, end, l, r);
        }
    }
    void update(int node, int start, int end, int idx, int v) {
        if (start == end) {
            seg[node] = v;
        }
        else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(node*2, start, mid, idx, v);
            }
            else update(node*2+1, mid+1, end, idx, v);
            seg[node] = seg[node*2] + seg[node*2+1];
        }
    }
    public:
    void init(int nn) {
        n = nn;
        seg.assign(n*4+10, 0);
    }
    int query(int l, int r) {
        return query(1, 1, n, l, r);
    }
    void update(int idx, int v) {
        update(1, 1, n, idx, v);
    }
};

int main() {
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    cin >> n >> q;
    segTree dec, inc;
    dec.init(n);
    inc.init(n);
    for (int i = 1; i <= n; i++) {
        dec.update(i, 1);
        inc.update(i, 1);
    }
    vector<int> vals(n+1, 0);
    for (int qq = 1; qq <= n + q - 1; qq++) {
        char s; cin >> s;
        if (s == 'Q') {
            int a, b; cin >> a >> b;
            if (abs(a - b) == 1 && vals[max(a, b)] != 0) {
                cout << "yes\n";
                continue;
            }
            if (a == b) {
                cout << "yes\n";
                continue;
            }
            int tot = 0;
            if (a > b) {
                tot = inc.query(b+1, a);
            }
            else tot = dec.query(a+1, b);
            if (tot) cout << "no\n";
            else cout << "yes\n";
        }
        else if (s == 'S') {
            int a, b; cin >> a >> b;
            if (a > b) swap(a, b);
            vals[b] = qq;
            if (vals[b-1] == 0) {
                dec.update(b, 0);
                inc.update(b, 0);
            }
            else {
                if (vals[b-1] < vals[b]) {
                    inc.update(b, 0);
                }
                else dec.update(b, 0);
            }
            if (b < n && vals[b+1] != 0) {
                if (vals[b] < vals[b+1]) {
                    inc.update(b+1, 0);
                }
                else dec.update(b+1, 0);
            }
        }
        else assert(false);
    }
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18