Submission #1029931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029931		hengliao	Flooding Wall (BOI24_wall)	C++17	100 / 100	3321 ms	85040 KiB

Main

#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=5e5+5;
const ll mod=1e9+7;

ll pw[mxN];

struct segtree{
    vll tree, lazy;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcount(treelen)!=1){
            treelen++;
        }
        tree.resize(2*treelen);
        lazy=vll(2*treelen, 1);
    }

	void build(ll idx, ll low, ll high, vll &a){
		if(low==high){
			if(low<a.size()) tree[idx]=a[low];
			else tree[idx]=0;
			return;
		}
		ll mid=(low+high)/2;
		build(2*idx, low, mid, a);
		build(2*idx+1, mid+1, high, a);
		tree[idx]=tree[2*idx]+tree[2*idx+1];
		tree[idx]%=mod;
	}

    void push(ll idx, ll low, ll high){
        if(low!=high){
            lazy[2*idx]*=lazy[idx];
			lazy[2*idx]%=mod;
            lazy[2*idx+1]*=lazy[idx];
			lazy[2*idx+1]%=mod;
        }
    }

    void check(ll idx, ll low, ll high){
        tree[idx]*=lazy[idx];
		tree[idx]%=mod;
        push(idx, low, high);
        lazy[idx]=1;
    }

    void update1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
        check(idx, low, high);
        if(low>=qlow && high<=qhigh){
            lazy[idx]*=val;
			lazy[idx]%=mod;
            check(idx, low, high);
            return;
        }
        if(low>qhigh || high<qlow){
            return;
        }
        ll mid=(low+high)/2;
        update1(2*idx, low, mid, qlow, qhigh, val);
        update1(2*idx+1, mid+1, high, qlow, qhigh, val);
        tree[idx]=tree[2*idx]+tree[2*idx+1];
		tree[idx]%=mod;
    }

    ll getsum1(ll idx, ll low, ll high, ll qlow, ll qhigh){
        check(idx, low, high);
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return 0LL;
        }
        ll mid=(low+high)/2;
        return (getsum1(2*idx, low, mid, qlow, qhigh)+
		getsum1(2*idx+1, mid+1, high, qlow, qhigh))%mod;
    }

    void update(ll qlow, ll qhigh, ll val){
        update1(1, 0, treelen-1, qlow, qhigh, val);
    }

    ll getsum(ll qlow, ll qhigh){
        return getsum1(1, 0, treelen-1, qlow, qhigh);
    }
};

segtree seg;

vll con;

ll id(ll tar){
	return lower_bound(con.begin(), con.end(), tar)-con.begin();
}

void solve(){
	ll n;
	cin>>n;
	vector<pll> a(n);
	for(auto &[x, y]:a){
		cin>>x;
	}
	for(auto &[x, y]:a){
		cin>>y;
	}
	for(auto &[x, y]:a){
		if(x>y){
			swap(x, y);
		}
	}
	for(auto &[x, y]:a){
		con.pb(x);
		con.pb(y);
	}
	sort(con.begin(), con.end());
	con.erase(unique(con.begin(), con.end()), con.end());
	ll siz=con.size();
	vll bas(siz);
	bas[0]=con[0];
	for(ll i=1;i<siz;i++){
		bas[i]=con[i]-con[i-1];
	}
	seg.init(siz);
	seg.build(1, 0, seg.treelen-1, bas);
	ll ans=0;
	vll cnt(siz);
	for(auto &[x, y]:a){
		cnt[id(x)]++;
		cnt[id(y)]++;
	}
	ll pre=0;
	for(ll i=0;i<siz;i++){
		ans+=((pre*pw[n-1])%mod)*bas[i];
		ans%=mod;
		pre+=cnt[i];
	}
	for(ll i=0;i<n;i++){
		ll id1=id(a[i].F);
		ll id2=id(a[i].S);
		seg.update(0, id1, 0);
		if(id2+1<siz) seg.update(id2+1, siz-1, 2);
		ans-=seg.getsum(0, siz-1)*pw[n-i-1];
		ans%=mod;
		if(ans<0) ans+=mod;
	}
	seg.init(siz);
	seg.build(1, 0, seg.treelen-1, bas);
	for(ll i=n-1;i>=0;i--){
		ll id1=id(a[i].F);
		ll id2=id(a[i].S);
		seg.update(0, id1, 0);
		if(id2+1<siz) seg.update(id2+1, siz-1, 2);
		ans-=seg.getsum(0, siz-1)*pw[i];
		ans%=mod;
		if(ans<0) ans+=mod;
	}
	ans+=seg.getsum(0, siz-1)*n;
	ans%=mod;
	cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	pw[0]=1;
	for(ll i=1;i<mxN;i++){
		pw[i]=pw[i-1]*2;
		pw[i]%=mod;
	}

	solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::build(ll, ll, ll, std::vector<long long int>&)':
Main.cpp:33:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    if(low<a.size()) tree[idx]=a[low];
      |       ~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30