제출 #1129954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129954		Ludissey	Alternating Current (BOI18_alternating)	C++20	0 / 100	102 ms	15244 KiB

alternating

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

struct node {
    node* left;
    node* right;
    int sumMIN=0;
    int sum=0;
    int sumMAX=0;
    int lazy=0;
    int mnI=0;
    void update(){
        sumMIN=min(left->sumMIN,right->sumMIN);
        sumMAX=max(left->sumMAX,right->sumMAX);
        sum=left->sum+right->sum;
        if(left->sumMIN<=right->sumMIN) mnI=left->mnI;
        else mnI=right->mnI;
    }
};
 
struct segtree {
    int n;
    node* root=new node{nullptr,nullptr,0,0,0,0};
    void propagate(node* x){
        x->left->lazy+=x->lazy;
        x->right->lazy+=x->lazy;
        x->left->sum+=x->lazy;
        x->right->sum+=x->lazy;
        x->left->sumMIN+=x->lazy;
        x->right->sumMIN+=x->lazy;
        x->left->sumMAX+=x->lazy;
        x->right->sumMAX+=x->lazy;
        x->lazy=0;
    }
    void update(node* x, int l, int r, int qL, int qR, int v){
        if(l>qR||r<qL) return;
        if(l>=qL&&r<=qR){
            x->lazy+=v;
            x->sumMAX+=v;
            x->sumMIN+=v;
            x->sum+=v;
            return;
        }
        propagate(x);
        int mid=(l+r)/2;
        update(x->left,l,mid,qL,qR,v);
        update(x->right,mid+1,r,qL,qR,v);
        x->update();
    }
    void build(node* x, int l, int r){
        if(l==r){
            x->sumMIN=0;
            x->sumMAX=0;
            x->sum=0;
            x->mnI=l;
            return;
        }
        int mid=(l+r)/2;
        x->left=new node{nullptr,nullptr,0,(long long)0,0,0};
        x->right=new node{nullptr,nullptr,0,(long long)0,0,0};
        build(x->left,l,mid);
        build(x->right,mid+1,r);
        x->update();
    }
    int queryMAX(node* x, int l, int r, int qL, int qR){
        if(qR<l||r<qL) return -1e9;
        if(l>=qL&&r<=qR){
            return x->sumMAX;
        }
        propagate(x);
        int mid=(l+r)/2;
        int qs=max(queryMAX(x->left,l,mid,qL,qR),queryMAX(x->right,mid+1,r,qL,qR));
        return qs;
    }
    int queryMIN(node* x, int l, int r, int qL, int qR){
        if(qR<l||r<qL) return 1e9;
        if(l>=qL&&r<=qR){
            return x->sumMIN;
        }
        propagate(x);
        int mid=(l+r)/2;
        int q1=queryMIN(x->left,l,mid,qL,qR);
        int q2=queryMIN(x->right,mid+1,r,qL,qR);
        return min(q1,q2);
    }
    void update(int l, int r, int v){
        update(root,0,n-1,l,r,v);
    }
    int queryMAX(int l, int r){
        return queryMAX(root,0,n-1,l,r);
    }
    int queryMIN(int l, int r){
        return queryMIN(root,0,n-1,l,r);
    }
    segtree(int x){
        n=x;
        build(root,0,n-1);
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m; cin >> n >> m;
    segtree rem(n);
    vector<pair<int,int>> edge(m);
    for (int i = 0; i < m; i++)
    {
        int a,b; cin >> a >> b; a--; b--;
        edge[i]={a,b};
        if(a<=b){
            rem.update(a,b,1);
        }else{
            rem.update(a,n-1,1);
            rem.update(0,b,1);
        }
    }
    if(rem.queryMIN(0,n-1)<2) { cout << "impossible\n"; return 0; }
    vector<int> out(n,0);
    for (int i = 0; i < m; i++)
    {
        int a=edge[i].first,b=edge[i].second;
        int q=0;
        if(a<=b){
            q=rem.queryMIN(a,b);
        }else{
            q=min(rem.queryMIN(a,n-1),rem.queryMIN(0,b));
        }
        if(q<=1) continue;
        else{
            if(a<=b){
                rem.update(a,b,-1);
            }else{
                rem.update(a,n-1,-1);
                rem.update(0,b,-1);
            }
            out[i]=1;
        }
    }
    for (int i = 0; i < m; i++) cout << out[i];
    cout << "\n";
    return 0;
}

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