Submission #1138582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138582		hgmhc	Alternating Current (BOI18_alternating)	C++20	19 / 100	106 ms	23972 KiB

alternating

#include<bits/stdc++.h>
using namespace std; using ll = long long;
const ll N = 1e5 + 3, M = N;
int opposite[M]; // 없으면 0, 있으면 번호
int c[2*N]; // 해당 영역의 colored 여부
ll n, m;
vector<array<ll,3>> Ranges;
int bit[M]; // 현재 red:1, blue:2

struct segtree {
    struct node {
        int v;
        int z;
        node(): v(0), z(0) {}
    } t[N<<2];
    void push(int k, int s, int e) {
        t[k].v+=t[k].z;
        if (s!=e) {
            t[2*k].z+=t[k].z;
            t[2*k+1].z+=t[k].z;
        }
        t[k].z=0;
    }
    void add(int l, int r, int v, int k=1, int s=1, int e=n) {
        push(k,s,e);
        if (e<l||r<s) return;
        if (l<=s&&e<=r) {t[k].z+=v, push(k,s,e); return;}
        int m=(s+e)>>1;
        add(l,r,v,2*k,s,m);
        add(l,r,v,2*k+1,m+1,e);
        t[k].v=min(t[2*k].v, t[2*k+1].v);
    }
    int qry(int l, int r, int k=1, int s=1, int e=n) {
        push(k,s,e);
        if (e<l||r<s) return 1e9;
        if (l<=s&&e<=r) return t[k].v;
        int m=(s+e)>>1;
        return min(qry(l,r,2*k,s,m), qry(l,r,2*k+1,m+1,e));
    }
} Red, Blue;

void solve() {
    
    for (ll k=0; auto [l,r,name] : Ranges) {
        k++;
        if (k&1) {
            bit[name]=1;
            if (r<=n) Red.add(l,r,1);
            else Red.add(l,n,1), Red.add(1,r-n,1);
        }
        else {
            bit[name]=2;
            if (r<=n) Blue.add(l,r,1);
            else Blue.add(l,n,1), Blue.add(1,r-n,1);
        }
    }
    
    auto good = []() {
        return Red.qry(1,n) > 0 && Blue.qry(1,n) > 0;
    };
    
    if (good()) return;
    
    auto red_to_blue = [](int l, int r) {
        if (r<=n) {
            Red.add(l,r, -1);
            Blue.add(l,r, +1);
        }
        else {
            Red.add(l,r-n, -1);
            Blue.add(l,r-n, +1);
            Red.add(1,r, -1);
            Blue.add(1,r, +1);
        }
    };
    
    auto blue_to_red = [](int l, int r) {
        if (r<=n) {
            Blue.add(l,r, -1);
            Red.add(l,r, +1);
        }
        else {
            Blue.add(l,r-n, -1);
            Red.add(l,r-n, +1);
            Blue.add(1,r, -1);
            Red.add(1,r, +1);
        }
    };
    
    for (ll k=0; auto [l,r,name] : Ranges) {
        k++;
        if (k&1) {
            bit[name]=2;
            red_to_blue(l,r);
            if (good()) return;
        }
        else {
            bit[name]=1;
            blue_to_red(l,r);
            if (good()) return;
        }
    }
    
    cout << "impossible";
    exit(0);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    vector<array<ll,3>> R;
    for(ll i=1; i<=m; ++i) {
        int l, r; cin >> l >> r;
        if (l-1 == r) {
            R.push_back({1,n,i});
            R.push_back({n,2*n,i});
        }
        else if (l > r) {
            R.push_back({l,r+n, i});
        }
        else {
            R.push_back({l,r, i});
            R.push_back({l+n,r+n, i});
        }
    }
    sort(begin(R),end(R),[](auto &x, auto &y) {
        if (x[0]==y[0]) return x[1]>y[1];
        return x[0]<y[0];
    });
    auto cmp = [](const array<ll,3> &x, const array<ll,3> &y) {
        if (x[1] != y[1]) return x[1] > y[1];
        return x[2] < y[2]; // 모든 range의 이름은 구분되기 때문에..
    };
    set<array<ll,3>,decltype(cmp)> reduced_ranges;
    for(ll i=0; i<size(R); ++i) if (!opposite[R[i][2]]) {
        if (!empty(reduced_ranges) && R[i][1] <= reduced_ranges.begin()->at(1)) {
            c[R[i][0]]++;
            c[R[i][1]+1]--;
            opposite[R[i][2]] = reduced_ranges.begin()->at(2);
        }
        else {
            reduced_ranges.insert(R[i]);
        }
    }
    for(ll i=1; i<=2*n; ++i) {
        c[i] += c[i-1];
        if (i>n && c[i]) {
            c[i-n]=1;
        }
    }
    for(ll i=1; i<=n; ++i) {
        c[i]=(c[i]>0);
        if (c[i]) Red.add(i,i,+1), Blue.add(i,i,+1);
    }
    
    for (auto [l,r,k] : reduced_ranges) {
        if (l>n&&r>n) {
            Ranges.push_back({l-n,r-n,k});
        }
        else {
            Ranges.push_back({l,r,k});
        }
    }
    
    ranges::sort(Ranges);
    Ranges.erase(unique(Ranges.begin(),Ranges.end()),end(Ranges));
    
    // for (auto [l,r,name] : Ranges) {
    //     cerr << l << ' ' << r << endl;
    // }
    
    solve();
    
    for(ll i=1; i<=m; ++i) {
        if (bit[i]) {
            cout << bit[i]-1;
        }
        else {
            int x = opposite[i];
            while (true) {
                if (bit[x]) break;
                x = opposite[x];
            }
            cout << (bit[x]%2);
        }
    }
}

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