Submission #714525

#	Time	Username	Problem	Language	Result	Execution time	Memory
714525		MohamedFaresNebili	Alternating Current (BOI18_alternating)	C++14	100 / 100	273 ms	12708 KiB

alternating

#include <bits/stdc++.h>

        using namespace std;

        int N, M, X[100005], Y[100005];
        int R[100005], ST[400005], lazy[400005];
        vector<int> adj[100005];

        void prop(int v, int l, int r) {
            if(l == r || !lazy[v]) 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;
                prop(v, l, r); 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 1000000007;
            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));
        }
        bool dfs(int v) {
            for(auto u : adj[v]) {
                if(R[u] == 0) {
                    R[u] = -R[v];
                    if(dfs(u)) return true;
                }
                else if(R[u] == R[v]) return true;
            }
            return false;
        }

        int32_t main()
        {
            ios_base::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            cin >> N >> M; int K = 0; set<int> S;
            vector<pair<int, int>> P;
            for(int l = 0; l < M; l++) {
                cin >> X[l] >> Y[l]; X[l]--, Y[l]--;
                if(X[l] > Y[l]) S.insert(l);
                P.push_back({X[l], -l - 1});
                P.push_back({Y[l], l});
            }
            sort(P.begin(), P.end());
            for(int l = 0; l < N; l++) {
                while(K < P.size() && P[K] < make_pair(l, 0)) {
                    if(P[K].second < 0) S.insert(-P[K].second - 1);
                    else S.erase(P[K].second);
                    K++;
                }
                if(S.size() < 2) { cout << "impossible\n"; return 0; }
                if(S.size() == 2) {
                    int U = *S.begin();
                    int V = *next(S.begin());
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
            }
            for(int l = 0; l < M; l++) {
                if(R[l] == 0 && adj[l].size() > 0) {
                    R[l] = -1;
                    if(dfs(l)) { cout << "impossible\n"; return 0; }
                }
            }
            for(int l = 0; l < M; l++) {
                if(R[l] >= 0) {
                    if(X[l] <= Y[l])
                        update(1, 0, N - 1, X[l], Y[l], 1);
                    else update(1, 0, N - 1, 0, Y[l], 1),
                        update(1, 0, N - 1, X[l], N - 1, 1);
                }
            }
            for(int l = 0; l < M; l++) {
                if(!R[l]) {
                    int T = 1000000007;
                    if(X[l] <= Y[l])
                        T = query(1, 0, N - 1, X[l], Y[l]);
                    else T = min(query(1, 0, N - 1, 0, Y[l]),
                            query(1, 0, N - 1, X[l], N - 1));
                    if(T <= 1) R[l] = 1;
                    else {
                        R[l] = -1;
                        if(X[l] <= Y[l])
                            update(1, 0, N - 1, X[l], Y[l], -1);
                        else update(1, 0, N - 1, 0, Y[l], -1),
                            update(1, 0, N - 1, X[l], N - 1, -1);
                    }
                }
            }
            for(int l = 0; l < M; l++)
                cout << (R[l] == -1 ? 0 : 1);
        }

Compilation message (stderr)

alternating.cpp: In function 'int32_t main()':
alternating.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while(K < P.size() && P[K] < make_pair(l, 0)) {
      |                       ~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26