Submission #1004384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004384		PenguinsAreCute	Flooding Wall (BOI24_wall)	C++17	100 / 100	2568 ms	99964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int HALF = 5e8 + 4;
vector<int> disc;
struct seg {
	int n, h; vector<int> v, lazy;
	seg(int _n): n(_n), h(64-__builtin_clzll(_n)), lazy(2*_n,1), v(2*_n) {
		for(int i=0;i<n;i++) v[i+n]=disc[i+1]-disc[i];
		for(int i=n;i--;) {v[i]=v[i<<1]+v[i<<1|1]; if(v[i]>=MOD) v[i]-=MOD;}
	}
	void calc(int x) {v[x]=(v[x<<1]+v[x<<1|1])*lazy[x]%MOD;}
	void app(int x, int k) {
		(v[x]*=k)%=MOD;
		if(x<n) (lazy[x]*=k)%=MOD;
	}
	void push(int x) {
		int s=h;
		for(x+=n;s;s--) {
			int i=x>>s;
			app(i<<1,lazy[i]);
			app(i<<1|1,lazy[i]);
			lazy[i]=1;
		}
	}
	void build(int x) {for(x+=n;x>>=1;) calc(x);}
	void up(int x, int y, int m) {
		push(x); push(y-1);
		int x0 = x, y0 = y;
		for(x+=n,y+=n;x<y;x>>=1,y>>=1) {
			if(x&1) app(x++,m);
			if(y&1) app(--y,m);
		}
		build(x0); build(y0-1);
	}
};
main() {
	int n; cin >> n;
	int a[n], b[n];
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=0;i<n;i++) disc.push_back(a[i]),disc.push_back(b[i]);
	disc.push_back(0);
	sort(disc.begin(),disc.end());
	while(disc.size()<=(1<<20)) disc.push_back(1<<30);
	int aa[n], bb[n];
	for(int i=0;i<n;i++) {
		if(a[i]>b[i]) swap(a[i],b[i]);
		aa[i]=lower_bound(disc.begin(),disc.end(),a[i])-disc.begin();
		bb[i]=lower_bound(disc.begin(),disc.end(),b[i])-disc.begin();
	}
	seg sl(1<<20), sr(1<<20);
	int ansl[n], ansr[n];
	int ans = 0;
	for(int i=0;i<n;i++) {
		sl.up(0,aa[i],0);
		sl.up(aa[i],bb[i],HALF);
		ans-=sl.v[1];
	}
	for(int i=n;i--;) {
		sr.up(0,aa[i],0);
		sr.up(aa[i],bb[i],HALF);
		ans-=sr.v[1];
	}
	for(int i=0;i<n;i++) ans-=(HALF*(a[i]+b[i]))%MOD;
	(ans += (n<<30) + n * sl.v[1]) %= MOD;
	if(ans<0) ans+=MOD;
	for(int i=0;i<n;i++) {ans<<=1; if(ans>=MOD) ans-=MOD;}
	cout << ans;
}

Compilation message (stderr)

Main.cpp: In constructor 'seg::seg(long long int)':
Main.cpp:8:27: warning: 'seg::lazy' will be initialized after [-Wreorder]
    8 |  int n, h; vector<int> v, lazy;
      |                           ^~~~
Main.cpp:8:24: warning:   'std::vector<long long int> seg::v' [-Wreorder]
    8 |  int n, h; vector<int> v, lazy;
      |                        ^
Main.cpp:9:2: warning:   when initialized here [-Wreorder]
    9 |  seg(int _n): n(_n), h(64-__builtin_clzll(_n)), lazy(2*_n,1), v(2*_n) {
      |  ^~~
Main.cpp: At global scope:
Main.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:54:6: warning: unused variable 'ansl' [-Wunused-variable]
   54 |  int ansl[n], ansr[n];
      |      ^~~~
Main.cpp:54:15: warning: unused variable 'ansr' [-Wunused-variable]
   54 |  int ansl[n], ansr[n];
      |               ^~~~

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