Submission #696329

#	Time	Username	Problem	Language	Result	Execution time	Memory
696329		Cross_Ratio	Bread First Search (CCO21_day2problem2)	C++14	25 / 25	154 ms	16172 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int B[200005];
vector<int> adj[200005];
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) seg[i] = -1e9;
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n] = max(seg[n], k);
            return;
        }
        int mid = ns + ne >> 1;
        add(s, e, k, 2*n, ns, mid);
        add(s, e, k, 2*n+1, mid, ne);
    }
    int get_val(int n) {
        n += MAX/2;
        int v = seg[n];
        while(n != 0) {
            v = max(v, seg[n]);
            n /= 2;
        }
        return v;
    }
};
set<int> S;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=1;i<=N;i++) B[i] = i;
    for(i=0;i<M;i++) {
        int a, b;
        cin >> a >> b;
        if(a > b) swap(a, b);
        B[a] = max(B[a], b);
        adj[a].push_back(b);
    }
    SegTree tree(N+3);
    int MAX = tree.MAX;
    tree.add(1, 2, 0, 1, 0, MAX/2);
    int ma = 1;
    for(i=1;i<=N;i++) {
        ma = max(ma, B[i]);
        int v = tree.get_val(i);
        S.erase(i);
        for(int n : adj[i]) {
            S.insert(n);
        }
        //cout << v << ' ' << S.size() << '\n';
        //cout << i << " : " << ma << ' ' << v + (int)S.size() << '\n';
        tree.add(ma, N+1, v + (int)S.size(), 1, 0, MAX/2);
    }
    cout << N-1 - tree.get_val(N);
}

Compilation message (stderr)

Main.cpp: In member function 'void SegTree::add(int, int, int, int, int, int)':
Main.cpp:21:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:42:12: warning: unused variable 'j' [-Wunused-variable]
   42 |     int i, j;
      |            ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 14 / 14