Submission #233721

#	Time	Username	Problem	Language	Result	Execution time	Memory
233721		Charis02	Port Facility (JOI17_port_facility)	C++14	0 / 100	5 ms	384 KiB

port_facility

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

ll n,mod=1e9+7;
pi ar[N];
ll seg[4*N][2];
ll lazy[4*N][2];

void relax(ll low,ll high,ll pos,ll id)
{
    if(lazy[pos][id])
    {
        seg[pos][id]+=lazy[pos][id];

        if(low != high)
        {
            lazy[pos*2+1][id]+=lazy[pos][id];
            lazy[pos*2+2][id]+=lazy[pos][id];
        }

        lazy[pos][id]=0;
    }

    return;
}

void update(ll low,ll high,ll pos,ll slow,ll shigh,ll id)
{
    relax(low,high,pos,id);
    if(low>=slow&&high<=shigh)
    {
        lazy[pos][id]++;
        relax(low,high,pos,id);
        return;
    }
    if(low>shigh||high<slow)
        return;
    update(low,mid,pos*2+1,slow,shigh,id);
    update(mid+1,high,pos*2+2,slow,shigh,id);
    seg[pos][id]=seg[pos*2+1][id]+seg[pos*2+2][id];
    return;
}

ll query(ll low,ll high,ll pos,ll slow,ll id)
{
    relax(low,high,pos,id);
    if(low==high&&low==slow)
        return seg[pos][id];
    if(low>slow||high<slow)
        return 0;
    return query(low,mid,pos*2+1,slow,id)+query(mid+1,high,pos*2+2,slow,id);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    rep(i,0,n)
    {
        cin >> ar[i].first >> ar[i].second;
    }

    sort(ar,ar+n);
    ll ans = 1;

    rep(i,0,n)
    {
        ll q1_left = query(0,2*n,0,ar[i].first,0);
        ll q1_right = query(0,2*n,0,ar[i].second,0);
        ll q2_left = query(0,2*n,0,ar[i].first,1);
        ll q2_right = query(0,2*n,0,ar[i].second,1);

      //  cout << i << ": " << q1_left << " " << q1_right << "  " << q2_left << " " << q2_right << " ";

        if(q1_left != q1_right && q2_left != q2_right)
        {
            ans = 0;
        }
        else if(q1_left != q1_right)
        {
          //  cout << "upd q2";
            update(0,2*n,0,ar[i].first,ar[i].second,1);
        }
        else if(q2_left != q2_right)
        {
         //   cout << "upd q1";
            update(0,2*n,0,ar[i].first,ar[i].second,0);
        }
        else
        {
          //  cout << "both, upd q1";
            update(0,2*n,0,ar[i].first,ar[i].second,0);
            ans = (ans*2)%mod;
        }

     //   cout << endl;
    }

    cout << ans;

    return 0;
}

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