제출 #1286913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286913		minhjulzi	Inside information (BOI21_servers)	C++17	100 / 100	350 ms	94088 KiB

servers

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

#define task "task"
#define bit(x, i) ((x >> i) & 1)

// https://trap.jp/post/1224/
#define FOR1(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FOR2(i, a, b, c) for(int i = (a), _b = (b); i <= _b; i += c)
#define FORD1(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)
#define FORD2(i, a, b, c) for(int i = (a), _b = (b); i >= _b; i -= c)
#define overload4(a, b, c, d, name, ...) name
#define FOR(...) overload4(__VA_ARGS__, FOR2, FOR1)(__VA_ARGS__)
#define FORD(...) overload4(__VA_ARGS__, FORD2, FORD1)(__VA_ARGS__)

#define pb emplace_back
#define pf emplace_front
#define ins emplace
#define mp make_pair
#define fi first
#define se second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 1.6e6 + 5;
const int M = 3.5e7 + 5;
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int base = 31;
int n, k;
int root[N];
struct PersistentSegmentTree{
    #define lc st[id].l
    #define rc st[id].r
    int n;
    struct Node{
        int l, r, val;
    } st[M];
    int cur = 0;
    void init(int _n){
        n = _n;
    }
    int build(int l, int r){
        int id = ++ cur;
        if(l == r){
            st[id].val = 0;
            return id;
        };
        int mid = l + r >> 1;
        lc = build(l, mid);
        rc = build(mid + 1, r);
        st[id].val = st[lc].val + st[rc].val;
        return id;
    }
    int update(int pre, int l, int r, int pos, int val){
        int id = ++ cur;
        st[id] = st[pre];
        if(l == r){
            st[id].val = val;
            return id;
        }
        int mid = l + r >> 1;
        if(pos <= mid){
            rc = st[pre].r;
            lc = update(st[pre].l, l, mid, pos, val);
        }
        else{
            lc = st[pre].l;
            rc = update(st[pre].r, mid + 1, r, pos, val);
        }
        st[id].val = st[lc].val + st[rc].val;
        return id;
    }
    int query(int id, int l, int r, int u, int v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return st[id].val;
        int mid = l + r >> 1;
        return query(lc, l, mid, u, v) + query(rc, mid + 1, r, u, v);
    }
    void upd(int v, int pos, int val){
        root[v] = update(root[v], 1, n, pos, val);
    }
    int get(int v, int l, int r){
        return query(root[v], 1, n, l, r);
    }
    int merge(int v1, int v2, int l, int r){
        if(v1 == 0 || v2 == 0)
            return v1 + v2;
        int id = ++cur;
        if(l == r){
            st[id].val = st[v1].val + st[v2].val;
            return id;
        }
        int mid = l + r >> 1;
        lc = merge(st[v1].l, st[v2].l, l, mid);
        rc = merge(st[v1].r, st[v2].r, mid + 1, r);
        st[id].val = st[lc].val + st[rc].val;
        return id;
    }
} pst;
int ver = 1;
struct Query{
    char type;
    int a, b;
};
vector<Query> queries;
void solve(){
    cin>>n>>k;
    pst.init(n);
    root[0] = pst.build(1, n);
    FOR(i, 1, n){
        root[i] = ++pst.cur;
        pst.upd(i, i, 1);
    }
    FOR(i, 1, n) root[i + n] = ++pst.cur;
    FOR(i, 1, n + k - 1){
        char type; int a, b; cin>>type>>a;
        if(type != 'C') cin>>b;
        queries.push_back({type, a, b});
    }
    int cnt = n - 1;
    FORD(i, n + k - 2, 0){
        auto [type, a, b] = queries[i];
        if(type == 'S'){
            root[a + n] = pst.update(root[a + n], 1, n - 1, cnt, 1);
            root[b + n] = pst.merge(root[b + n], root[a + n], 1, n - 1);
            root[a + n] = root[b + n];
            cnt --;
        }
    }
    // cout<<pst.cur;
    FOR(i, 0, n + k - 2){
        auto [type, a, b] = queries[i];
        if(type == 'S'){
            root[a] = root[b] = pst.merge(root[a], root[b], 1, n);
            cnt ++;
        }
        else if(type == 'Q')
            cout<<(pst.get(a, b, b) ? "yes\n" : "no\n");
        else
            cout<<pst.query(root[a + n], 1, n - 1, 1, cnt) + 1<<'\n';
    }
}
bool M2;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
    // cin>>tc;
    while(tc --) solve();
    cerr << "\nMemory: " << abs(&M2-&M1)/1024.0/1024 << " Mb\n";
    cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'int main()':
servers.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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