Submission #672149

#	Time	Username	Problem	Language	Result	Execution time	Memory
672149		urosk	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	212 KiB

port_facility

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 1000005
#define mod 1000000007
ll n;
pll a[maxn];
pll t[4*maxn];
ll t2[4*maxn],lazy[4*maxn];
ll ans = 1;
void upd(ll v,ll tl,ll tr,ll i,pll p){
    if(tl==tr){t[v] = p;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(2*v,tl,mid,i,p);
    else upd(2*v+1,mid+1,tr,i,p);
    t[v] = max(t[2*v],t[2*v+1]);
}
pll get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {0,0};
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void push(ll v,ll tl,ll tr){
    t2[v]+=(tr-tl+1)*lazy[v];
    if(tl<tr){
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
    }
    lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
    push(v,tl,tr);
    if(l>r) return;
    if(tl==l&&tr==r){
        lazy[v]+=x;
        push(v,tl,tr);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(2*v,tl,mid,l,min(mid,r),x);
    upd(2*v+1,mid+1,tr,max(mid+1,l),r,x);
    t2[v] = t2[2*v]+t2[2*v+1];
}
ll get2(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return 0;
    if(tl==l&&tr==r) return t2[v];
    ll mid = (tl+tr)/2;
    return get2(2*v,tl,mid,l,min(mid,r)) + get2(2*v+1,mid+1,tr,max(mid+1,l),r);
}
bool vis[maxn];
bool cmp(ll x,ll y){
    return a[x].sc-a[x].fi<a[y].sc-a[y].fi;
}
int main()
{
    cout<<0<<endl;
    return 0;
    cin >> n;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    sort(a+1,a+1+n);
    for(ll i = 1;i<=n;i++) upd(1,1,2*n,a[i].fi,{a[i].sc,i});
    queue<ll> q;
    vector<ll> v;
    for(ll i = 1;i<=n;i++){
        if(vis[i]) continue;
        q.push(i);
        upd(1,1,2*n,a[i].fi,{0,0});
        while(sz(q)){
            ll j = q.front();
            q.pop();
            v.clear();
            vis[j] = 1;
            ll l = a[j].fi,r = a[j].sc;
            while(1){
                pll p = get(1,1,2*n,l,r);
                if(p.fi<r) break;
                ll x = p.sc;
                v.pb(x);
                q.push(x);
                upd(1,1,2*n,a[x].fi,{0,0});
            }
            for(ll x : v) upd(1,1,2*n,a[x].fi,a[x].sc,1);
            sort(all(v),cmp);
            ll last = 0,lastsz = 0,cnt = sz(v);
            for(ll x : v){
                ll cur = get2(1,1,2*n,a[x].fi,a[x].sc);
                if(cur!=last+cnt*(a[x].sc-a[x].fi+1-lastsz)){
                    cout<<0<<endl;
                    return 0;
                }
                last = cur;
                lastsz = a[x].sc-a[x].fi+1;
                cnt--;
            }
            for(ll x : v) upd(1,1,2*n,a[x].fi,a[x].sc,-1);
        }
        ans*=2;
        if(ans>=mod) ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}
/*
4
1 3
2 5
4 8
6 7
ans: 4

3
1 4
2 5
3 6
ans: 0

5
1 4
2 10
6 9
7 8
3 5
ans: 8

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12
ans: 16

*/

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