Submission #505180

#	Time	Username	Problem	Language	Result	Execution time	Memory
505180		mjhmjh1104	Alternating Current (BOI18_alternating)	C++17	100 / 100	286 ms	12208 KiB

alternating

#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;

int tree[262144], lazy[262144];

void propagate(int i, int b, int e) {
    if (!lazy[i]) return;
    if (b != e) {
        lazy[i * 2 + 1] += lazy[i];
        lazy[i * 2 + 2] += lazy[i];
    }
    tree[i] += lazy[i];
    lazy[i] = 0;
}

int query(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[i];
    int m = (b + e) / 2;
    return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}

int update(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < b || e < l) return tree[i];
    if (l <= b && e <= r) {
        lazy[i] += v;
        propagate(i, b, e);
        return tree[i];
    }
    int m = (b + e) / 2;
    return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}

int n, m, x[100006], y[100006];
vector<int> adj[100006];
set<int> s;
vector<pair<int, int>> v;
int cl[100006];

bool dfs(int x) {
    for (auto &i: adj[x]) {
        if (!cl[i]) {
            cl[i] = -cl[x];
            if (dfs(i)) return true;
        } else if (cl[i] == cl[x]) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", x + i, y + i);
        x[i]--, y[i]--;
        if (x[i] > y[i]) s.insert(i);
        v.push_back({ x[i], -i - 1 });
        v.push_back({ y[i], i });
    }
    sort(v.begin(), v.end());
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k < (int)v.size() && v[k] < make_pair(i, 0)) {
            if (v[k].second < 0) s.insert(-v[k].second - 1);
            else s.erase(v[k].second);
            k++;
        }
        if ((int)s.size() < 2) return puts("impossible"), 0;
        if ((int)s.size() == 2) {
            int first = *s.begin();
            int second = *next(s.begin());
            adj[first].push_back(second);
            adj[second].push_back(first);
        }
    }
    for (int i = 0; i < m; i++) if (!cl[i] && !adj[i].empty()) {
        cl[i] = -1;
        if (dfs(i)) return puts("impossible"), 0;
    }
    for (int i = 0; i < m; i++) if (cl[i] >= 0) {
        if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], 1);
        else update(0, 0, 131071, 0, y[i], 1), update(0, 0, 131071, x[i], n - 1, 1);
    }
    for (int i = 0; i < m; i++) if (!cl[i]) {
        int t = 0;
        if (x[i] <= y[i]) t = query(0, 0, 131071, x[i], y[i]);
        else t = min(query(0, 0, 131071, 0, y[i]), query(0, 0, 131071, x[i], n - 1));
        if (t <= 1) cl[i] = 1;
        else {
            cl[i] = -1;
            if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], -1);
            else update(0, 0, 131071, 0, y[i], -1), update(0, 0, 131071, x[i], n - 1, -1);
        }
    }
    for (int i = 0; i < m; i++) {
        if (cl[i] == -1) printf("0");
        else printf("1");
    }
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d%d", x + i, y + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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