Submission #941292

#	Time	Username	Problem	Language	Result	Execution time	Memory
941292		phoenix0423	Alternating Current (BOI18_alternating)	C++17	32 / 100	73 ms	12992 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;

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;
    }
    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;
        }
};

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 = 1, int L = 0, int R = n - 1){
    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]);
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
    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));
}
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);
}

bool ck(seg a){
    a.l %= n, a.r %= n;
    if(a.l <= a.r) return qry(a.l, a.r) >= 2;
    else return min(qry(a.l, n - 1), qry(0, a.r)) >= 2;
}
int getlen(int a, int b){
    return (b - a + n) % n + 1;
}
signed main(void){
    fastio;
    cin>>n>>m;
    vector<seg> e;
    int mx = 0;
    int st = 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        a += n, b += n;
        if(getlen(a, b) > mx) mx = getlen(a, b), st = a;
        insert(a, b, 1);
        e.pb(seg(a, b, i));
    }
    if(qry(0, n - 1) < 2){
        cout<<"impossible\n";
        return 0;
    }
    // for(int i = 0; i < m; i++){
    //     if(e[i].l < st) e[i].l += n;
    //     if(e[i].r < e[i].l) e[i].r += n;
    //     cout<<e[i].l<<" "<<e[i].r<<"\n";
    // }
    sort(e.begin(), e.end());
    int r = e[0].l - 1;
    vector<int> ans(m);
    int id = 0;
    priority_queue<seg, vector<seg>, comp> q;
    int dist = 0;
    while(true){
        // cout<<"r : "<<r<<"\n";
        while(id < m && e[id].l <= r + 1){
            // cout<<"push : "<<e[id].l<<" "<<e[id].r<<" "<<e[id].id<<"\n";
            q.push(e[id]);
            id++;
        }
        while(true){
            if(q.empty()){
                cout<<"impossible\n";
                return 0;
            }
            seg cur = q.top(); q.pop();
            if(!ck(cur)) continue;
            if(cur.r <= r) continue;
            // cout<<"use : "<<cur.l<<" "<<cur.r<<" "<<cur.id<<"\n";
            insert(cur.l, cur.r, -1);
            ans[cur.id] = 1;
            dist += cur.r - r;
            r = cur.r;
            break;
        }
        // cout<<dist<<"\n";
        if(dist >= n) break;
    }
    for(auto x : ans) cout<<x;
    cout<<"\n";
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:87:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
   87 |     int st = 0;
      |         ^~

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