Submission #627429

#	Time	Username	Problem	Language	Result	Execution time	Memory
627429		MohamedFaresNebili	Bread First Search (CCO21_day2problem2)	C++14	25 / 25	231 ms	14184 KiB

Main

#include <bits/stdc++.h>

            using namespace std;

            using ll = long long;
            using ld = long double;
            using pi = pair<pair<int, int>, pair<int, int>>;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
            #define int ll

            int N, M, ST[800005], lazy[800005], L[200005], R[200005];
            void prop(int v, int l, int r) {
                if(l == r) return;
                lazy[v * 2] += lazy[v];
                lazy[v * 2 + 1] += lazy[v];

                ST[v * 2] += lazy[v];
                ST[v * 2 + 1] += lazy[v];

                lazy[v] = 0; return;
            }
            void update(int v, int l, int r, int lo, int hi, int val) {
                prop(v, l, r);
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    ST[v] += val; lazy[v] += val;
                    return;
                }
                update(v * 2, l, (l + r) / 2, lo, hi, val);
                update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                ST[v] = min(ST[v * 2], ST[v * 2 + 1]);
            }
            int query(int v, int l, int r, int lo, int hi) {
                prop(v, l, r);
                if(l > hi || r < lo) return 1e9 + 7;
                if(l >= lo && r <= hi) return ST[v];
                return min(query(v * 2, l, (l + r) / 2, lo, hi),
                           query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 1; l <= N; l++) L[l] = l, R[l] = l;
                for(int l = 1; l <= M; l++) {
                    int U, V; cin >> U >> V;
                    L[V] = min(L[V], U); L[U] = min(L[U], V);
                    R[V] = max(R[V], U); R[U] = max(R[U], V);
                }
                int i = 1;
                for(int l = 2; l <= N; l++) {
                    while(i < l && R[i] <= l) i++;
                    update(1, 1, N, 1, L[l] - 1, 1);
                    int P = query(1, 1, N, 1, i - 1);
                    update(1, 1, N, l, l, P);
                }
                cout << ST[1] << "\n";
                return 0;
            }

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