Submission #442083

#	Time	Username	Problem	Language	Result	Execution time	Memory
442083		abc864197532	Alternating Current (BOI18_alternating)	C++17	100 / 100	344 ms	19492 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 100000;

struct Seg {
    int l, r, m, mn, lz;
    Seg* ch[2];
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), mn(0), lz(0) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
        }
    }
    void pull() {mn = min(ch[0]->mn, ch[1]->mn);}
    void give(int v) {mn += v, lz += v;}
    void push() {ch[0]->give(lz), ch[1]->give(lz), lz = 0;}
    void add(int a, int b, int v) {
        if (a <= l && r <= b) give(v);
        else {
            push();
            if (a < m) ch[0]->add(a, b, v);
            if (m < b) ch[1]->add(a, b, v);
            pull();
        }
    }
    int query(int a, int b) {
        if (a <= l && r <= b) return mn;
        push();
        int ans = 1 << 30;
        if (a < m) ans = min(ans, ch[0]->query(a, b));
        if (m < b) ans = min(ans, ch[1]->query(a, b));
        return ans;
    }
};

int color[N];
bool odd_cycle;
vector <int> adj[N];

void dfs(int v) {
    for (int u : adj[v]) {
        if (!color[u]) {
            color[u] = 3 ^ color[v];
            dfs(u);
        } else if (color[u] == color[v]) {
            odd_cycle = true;
        }
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> l(m), r(m);
    vector <pii> event;
    for (int i = 0; i < m; ++i) {
        cin >> l[i] >> r[i], --l[i];
        if (l[i] != r[i]) event.eb(l[i], i), event.eb(r[i], i);
        if (l[i] >= r[i]) event.eb(0, i);
    }
    sort(all(event));
    set <int> on;
    for (int i = 0, j = 0; i < n; ++i) {
        for (; j < event.size() && event[j].X == i; ++j) {
            if (on.count(event[j].Y)) on.erase(event[j].Y);
            else on.insert(event[j].Y);
        }
        if (on.size() < 2) return cout << "impossible\n", 0;
        else if (on.size() == 2) {
            int u = *on.begin(), v = *on.rbegin();
            adj[u].pb(v), adj[v].pb(u);
        }
    }
    for (int i = 0; i < m; ++i) if (!color[i] && !adj[i].empty()) {
        color[i] = 1;
        dfs(i);
    }
    if (odd_cycle) return cout << "impossible\n", 0;
    Seg root(0, n);
    auto add = [&](int i, int v) {
        if (l[i] >= r[i]) root.add(l[i], n, v), root.add(0, r[i], v);
        else root.add(l[i], r[i], v);
    };
    auto qry = [&](int i) {
        if (l[i] >= r[i]) return min(root.query(l[i], n), root.query(0, r[i]));
        return root.query(l[i], r[i]);
    };
    for (int i = 0; i < m; ++i) if (color[i] != 1) add(i, 1);
    for (int i = 0; i < m; ++i) if (!color[i]) {
        if (qry(i) == 1) color[i] = 2;
        else color[i] = 1, add(i, -1);
    }
    for (int i = 0; i < m; ++i) cout << color[i] - 1;
    cout << endl;
}

Compilation message (stderr)

alternating.cpp: In constructor 'Seg::Seg(int, int)':
alternating.cpp:25:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), mn(0), lz(0) {
      |                                            ~~^~~
alternating.cpp: In function 'int main()':
alternating.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (; j < event.size() && event[j].X == i; ++j) {
      |                ~~^~~~~~~~~~~~~~

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