Submission #1138571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138571		hgmhc	Alternating Current (BOI18_alternating)	C++20	19 / 100	81 ms	14408 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() {
    ranges::sort(Ranges);
    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;
    static array<ll,3> range[M];
    for(ll i=1; i<=m; ++i) {
        cin >> range[i][0] >> range[i][1];
        if (range[i][0] > range[i][1]) range[i][1] += n;
        range[i][2] = i;
    }
    sort(range+1, range+m+1, [](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=1; i<=m; ++i) {
        if (!empty(reduced_ranges) && range[i][1] <= reduced_ranges.begin()->at(1)) {
            c[range[i][0]]++;
            c[range[i][1]+1]--;
            opposite[range[i][2]] = reduced_ranges.begin()->at(2);
        }
        else {
            reduced_ranges.insert(range[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);
    }
    Ranges.insert(end(Ranges), begin(reduced_ranges), end(reduced_ranges));
    
    solve();
    
    for(ll i=1; i<=m; ++i) {
        if (bit[i]) {
            cout << bit[i]-1;
        }
        else {
            assert(opposite[i]);
            cout << (bit[opposite[i]]%2);
        }
    }
}

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