oj.uz

Submission #672008

# Submission time Handle Problem Language Result Execution time Memory
672008 2022-12-14T15:35:03 Z LittleCube Alternating Current (BOI18_alternating) C++14
0 / 100
 72 ms 11088 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, M, ans[100005], a[100005], b[100005];
vector<int> E[100005];

struct segTree
{
    int seg[400005], lazy[400005];

    int getval(int i)
    {
        return seg[i] + lazy[i];
    }

    void push(int i)
    {
        lazy[i << 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
        lazy[i] = 0;
    }

    void pull(int i)
    {
        seg[i] = min(getval(i << 1), getval(i << 1 | 1));
    }

    void modify(int mL, int mR, int val, int i = 1, int L = 1, int R = N)
    {
        if (mL <= L && R <= mR)
            lazy[i] += val;
        else if (R < mL || mR < L)
            return;
        else
        {
            int mid = (L + R) / 2;
            push(i);
            modify(mL, mR, val, i << 1, L, mid);
            modify(mL, mR, val, i << 1 | 1, mid + 1, R);
            pull(i);
        }
    }

    int query(int qL, int qR, int i = 1, int L = 1, int R = N)
    {
        if (qL <= L && R <= qR)
            return seg[i] + lazy[i];
        else if (R < qL || qR < L)
            return 0;
        else
        {
            int mid = (L + R) / 2;
            push(i);
            pull(i);
            return min(query(qL, qR, i << 1, L, mid), query(qL, qR, i << 1 | 1, mid + 1, R));
        }
    }
} seg;

bool dfs(int u)
{
    bool r = 1;
    for (int v : E[u])
        if (ans[v] == 0)
        {
            ans[v] = ans[u] ^ 3;
            r &= dfs(v);
        }
        else
            r &= (ans[u] ^ ans[v]) == 3;
    return r;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    set<int> sweep;
    vector<pii> event;
    for (int i = 1; i <= M; i++)
    {
        cin >> a[i] >> b[i];
        if (b[i] < a[i])
        {
            sweep.insert(i);
            event.emplace_back(pii(b[i] + 1, -i));
            event.emplace_back(pii(a[i], i));
        }
        else
        {
            event.emplace_back(pii(a[i], i));
            event.emplace_back(pii(b[i] + 1, -i));
        }
    }
    sort(event.begin(), event.end());
    for (int i = 1, j = 0; i <= N; i++)
    {
        while (j < event.size() && event[j].F == i)
        {
            auto [t, k] = event[j];
            if (k > 0)
                sweep.insert(k);
            else
                sweep.erase(-k);
            j++;
        }
        if (sweep.size() == 1)
        {
            cout << "impossible\n";
            return 0;
        }
        else if (sweep.size() == 2)
        {
            int u = *sweep.begin(), v = *next(sweep.begin());
            E[u].emplace_back(v);
            E[v].emplace_back(u);
        }
    }
    for (int i = 1; i <= M; i++)
        if (ans[i] == 0 && !E[i].empty())
        {
            ans[i] = 1;
            if (!dfs(i))
            {
                cout << "impossible\n";
                return 0;
            }
        }
    for (int i = 1; i <= M; i++)
        if (ans[i] <= 1)
        {
            if (b[i] < a[i])
            {
                seg.modify(a[i], N, 1);
                seg.modify(1, b[i], 1);
            }
            else
                seg.modify(a[i], b[i], 1);
        }
    for (int i = 1; i <= M; i++)
        if (!ans[i])
        {
            int rem;
            if (b[i] < a[i])
                rem = min(seg.query(a[i], N), seg.query(1, b[i]));
            else
                rem = seg.query(a[i], b[i]);
            if (rem >= 2)
            {
                ans[i] = 2;
                if (b[i] < a[i])
                {
                    seg.modify(a[i], N, -1);
                    seg.modify(1, b[i], -1);
                }
                else
                    seg.modify(a[i], b[i], -1);
            }
            else
                ans[i] = 1;
        }
    for (int i = 1; i <= M; i++)
        cout << ans[i] - 1;
    cout << '\n';
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:103: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]
  103 |         while (j < event.size() && event[j].F == i)
      |                ~~^~~~~~~~~~~~~~
alternating.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |             auto [t, k] = event[j];
      |                  ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct
16 Correct 2 ms 2680 KB Output is correct
17 Correct 2 ms 2680 KB Output is correct
18 Incorrect 1 ms 2684 KB no wires in direction 1 between segments 3 and 3
19 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct
16 Correct 2 ms 2680 KB Output is correct
17 Correct 2 ms 2680 KB Output is correct
18 Incorrect 1 ms 2684 KB no wires in direction 1 between segments 3 and 3
19 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct
16 Correct 2 ms 2680 KB Output is correct
17 Correct 2 ms 2680 KB Output is correct
18 Incorrect 1 ms 2684 KB no wires in direction 1 between segments 3 and 3
19 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 11088 KB Output is correct
2 Correct 5 ms 3684 KB Output is correct
3 Correct 14 ms 4672 KB Output is correct
4 Correct 55 ms 8504 KB Output is correct
5 Correct 69 ms 11088 KB Output is correct
6 Correct 38 ms 6344 KB Output is correct
7 Incorrect 67 ms 10808 KB no wires in direction 1 between segments 762 and 762
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct
16 Correct 2 ms 2680 KB Output is correct
17 Correct 2 ms 2680 KB Output is correct
18 Incorrect 1 ms 2684 KB no wires in direction 1 between segments 3 and 3
19 Halted 0 ms 0 KB -