Submission #1228461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228461		12345678	Alternating Current (BOI18_alternating)	C++17	52 / 100	111 ms	20000 KiB

alternating

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, m, l[nx], r[nx], vs[nx], qs[nx], c[nx], vss[nx], f;
vector<int> add[nx], rem[nx], d[nx];
set<int> cur;

void dfs(int u)
{
    vss[u]=1;
    for (auto v:d[u])
    {
        if (vss[v]&&c[u]==c[v]) f=1;
        if (!vss[v]) c[v]=!c[u], dfs(v); 
    }
}

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr ,vl);
        update(md+1, r, 2*i+1, ql, qr ,vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return INT_MAX;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

void addrange(int l, int r)
{
    if (l<=r) s.update(1, n, 1, l, r, 1);
    else s.update(1, n, 1, 1, r, 1), s.update(1, n, 1, l, n, 1);
}

int getmin(int l, int r)
{
    if (l<=r) return s.query(1, n, 1, l, r);
    else return min(s.query(1, n, 1, 1, r), s.query(1, n, 1, l, n));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>l[i]>>r[i];
        if (l[i]<=r[i]) add[l[i]].push_back(i), rem[r[i]].push_back(i);
        else rem[r[i]].push_back(i), add[l[i]].push_back(i), cur.insert(i);
    }
    for (int i=1; i<=n; i++)
    {
        qs[i]+=qs[i-1];
        for (auto x:add[i]) cur.insert(x);
        if (cur.size()<2) return cout<<"impossible", 0;
        if (cur.size()==2)
        {
            int u=*cur.begin(), v=*next(cur.begin());
            d[u].push_back(v);
            d[v].push_back(u);
            vs[u]=vs[v]=1;
        }
        for (auto x:rem[i]) cur.erase(x);
    }
    for (int i=1; i<=m; i++) if (vs[i]&&!vss[i]) dfs(i);
    if (f) return cout<<"impossible", 0;
    for (int i=1; i<=m; i++) if (c[i]) addrange(l[i], r[i]);
    for (int i=1; i<=m; i++)
    {
        if (!vs[i]) if (getmin(l[i], r[i])==0) addrange(l[i], r[i]), c[i]=1;
        //cout<<i<<' '<<c[i]<<' '<<vs[i]<<'\n';
        cout<<c[i];
    }
}

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