Submission #941355

#	Time	Username	Problem	Language	Result	Execution time	Memory
941355		phoenix0423	Alternating Current (BOI18_alternating)	C++17	19 / 100	72 ms	19596 KiB

alternating

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, m;
vector<int> adj[maxn];

struct seg{
    int l, r, id;
    seg(){}
    seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){
        if(r < l) r += n;
        else l += n, r += n;
    }
    bool operator < (const seg& other) const{
        if(l != other.l) return l < other.l;
        return r > other.r;
    }
};

class comp{
    public:
        bool operator ()(seg a, seg b){
            if(a.r != b.r) return a.r < b.r;
            else return a.l < b.l;
        }
};
struct segtree{
    int st[maxn * 4], tag[maxn * 4];
    void cast(int val, int v){
        st[v] += val, tag[v] += val;
    }

    void push(int v){
        if(tag[v]){
            cast(tag[v], v * 2);
            cast(tag[v], v * 2 + 1);
            tag[v] = 0;
        }
    }
    void upd(int l, int r, int val, int v, int L, int R){
        if(l > R || r < L) return;
        if(l <= L && r >= R){
            st[v] += val, tag[v] += val;
            return;
        }
        push(v);
        int m = (L + R) / 2;
        upd(l, r, val, v * 2, L, m);
        upd(l, r, val, v * 2 + 1, m + 1, R);
        st[v] = min(st[v * 2], st[v * 2 + 1]);
    }
    void upd(int l, int r, int val){ upd(l, r, val, 1, 0, n - 1);}
    int qry(int l, int r, int v, int L, int R){
        if(l > R || r < L) return INF;
        if(l <= L && r >= R) return st[v];
        push(v);
        int m = (L + R) / 2;
        return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
    }
    int qry(int l, int r){ return qry(l, r, 1, 0, n - 1);}
    void insert(int l, int r, int val){
        l %= n, r %= n;
        if(l <= r) upd(l, r, val);
        else upd(l, n - 1, val), upd(0, r, val);
    }
} st[2];

signed main(void){
    fastio;
    cin>>n>>m;
    vector<seg> e;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        e.pb(seg(a, b, i));
    }
    vector<int> par(m, -1);
    sort(e.begin(), e.end());
    int tr = -1, tid = -1;
    vector<seg> nw;
    for(int i = 0; i < m; i++){
        auto [l, r, id] = e[i];
        if(r <= tr) par[id] = tid, adj[tid].pb(i);
        else tr = r, tid = nw.size(), nw.pb(e[i]);
    }
    // for(int i = 0; i < m; i++) cout<<par[i]<<" ";
    // cout<<"\n";
    vector<int> ans(m);
    for(int i = 0; i < nw.size(); i++){
        st[i % 2].insert(nw[i].l, nw[i].r, 1);
        ans[nw[i].id] = i % 2;
        for(auto id : adj[i]){
            st[(i % 2 == 0)].insert(e[id].l, e[id].r, 1);
            ans[e[id].id] = (i % 2 == 0);
        }
    }
    if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
        for(auto x : ans) cout<<x;
        cout<<"\n";
        return 0;
    }
    if(nw.size() % 2 == 0){
        cout<<"impossible\n";
        return 0;
    }
    else{
        for(int i = 0; i < nw.size(); i++){
            st[i % 2].insert(nw[i].l, nw[i].r, -1);
            st[(i % 2 == 0)].insert(nw[i].l, nw[i].r, 1);
            ans[nw[i].id] ^= 1;
            for(auto id : adj[i]){
                st[(i % 2 == 0)].insert(e[id].l, e[id].r, -1);
                st[i % 2].insert(e[id].l, e[id].r, 1);
                ans[e[id].id] ^= 1;
            }
            if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
                for(auto x : ans) cout<<x;
                cout<<"\n";
                return 0;
            }
        }
        cout<<"impossible\n";
    }

}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:100:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
alternating.cpp:118:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

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