Submission #1101355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101355		irmuun	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	336 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll mod=1e9+7;

struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    vector<ll>a(n+1),b(n+1);
    vector<ll>event(2*n+1);
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        event[a[i]]=i;
        event[b[i]]=i;
    }
    vector<ll>col(n+1,-1);
    segtree sg0(2*n),sg1(2*n);
    ll ans=1;
    for(ll i=1;i<=2*n;i++){
        ll j=event[i];
        if(a[j]==i){
            vector<ll>cnt(2,0);
            cnt[0]=sg0.query(1,1,2*n,a[j],b[j]);
            cnt[1]=sg1.query(1,1,2*n,a[j],b[j]);
            if(cnt[0]+cnt[1]==0){
                ans=ans*2%mod;
                col[j]=0;
            }
            else if(cnt[0]>0&&cnt[1]>0){
                cout<<0;
                return 0;
            }
            else if(cnt[0]==0){
                col[j]=0;
            }
            else{
                col[j]=1;
            }
            if(col[j]==0){
                sg0.update(1,1,2*n,b[j],1);
            }
            else{
                sg1.update(1,1,2*n,b[j],1);
            }
        }
        else{
            if(col[j]==0) sg0.update(1,1,2*n,b[j],0);
            else sg1.update(1,1,2*n,b[j],0);
        }
    }
    cout<<ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22