Submission #1274764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274764		Bui_Quoc_Cuong	Flooding Wall (BOI24_wall)	C++20	100 / 100	3794 ms	325200 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pb push_back
#define sz(v) (int)v.size()
#define fi first
#define se second
#define ALL(A) A.begin(), A.end()
#define ll long long
#define pii pair <int, int>
#define vi vector <int>

#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define BIT(mask,i) ((mask>>(i))&1)
#define MASK(a) (1LL << (a))
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize (T& a, const T& b) {
	if (a > b) return a = b, true;
	return false;
}

template<typename T>
bool maximize (T& a, const T& b) {
	if (a < b) return a = b, true;
	return false;
}

const int N = (int) 5e5 + 5;
const int MOD = (int) 1e9 + 7;

int n;
int a[N], b[N];

void init(void) {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}
}

namespace sub1 {
	int power2[N], pref[N], suf[N];

	void solve() {
		vector <int> values;
		for (int i = 1; i <= n; i++) {
			values.push_back(a[i]);
			values.push_back(b[i]);
		}
		sort(values.begin(), values.end());
		values.resize(unique(ALL(values)) - values.begin());
		power2[0] = 1;
		for (int i = 1; i <= n; i++) {
			power2[i] = 1LL * power2[i - 1] * 2 % MOD;
		}

		pref[0] = suf[n + 1] = 1;
		int ans = 0;

		for (int it = 1; it < sz(values); it++) {
			for (int i = 1; i <= n; i++) {
				pref[i] = pref[i - 1];
				pref[i] = 1LL * pref[i] * ((a[i] < values[it]) + (b[i] < values[it])) % MOD;
			}
			for (int i = n; i >= 1; i--) {
				suf[i] = suf[i + 1];
				suf[i] = 1LL * suf[i] * ((a[i] < values[it]) + (b[i] < values[it])) % MOD;
			}	
			int cnt = 0;
			for (int i = 2; i < n; i++) {
				int wayLeft = (power2[i - 1] - pref[i - 1] + MOD) % MOD;
				int wayRight = (power2[n - i] - suf[i + 1] + MOD) % MOD;
				int wayI = ((a[i] < values[it]) + (b[i] < values[it]));
				int sum = 1LL * wayLeft * wayRight % MOD * wayI % MOD;
				(cnt+= sum) %= MOD;
			}
			(ans+= 1LL * cnt * (values[it] - values[it - 1]) % MOD) %= MOD;
		}	

		cout << ans;
	}
}

namespace sub2 {
	int power2[N];

	struct SegmentTreePre {
		struct Node {
			int ans, len, suf;
			Node () {
				ans = 0;
				len = 1;
				suf = 0;
			}
		} st[4 * N];
		friend Node operator + (Node a, Node b) {
			Node res;
			res.suf = 1LL * a.suf * b.suf % MOD;
			res.len = a.len + b.len;
			res.ans = 1LL * a.ans * b.suf % MOD + 1LL * power2[a.len] * b.ans % MOD;
			res.ans %= MOD;
			return res;
		}
		void update (int pos, int val) {
			int id = 1, l = 1, r = n;
			while (l < r) {
				int mid = (l + r) >> 1;
				if (pos <= mid) id = id << 1, r = mid;
				else id = id << 1 | 1, l = mid + 1;
			}
			st[id].suf+= val;
			st[id].ans+= val;
			while (id > 1) {
				id >>= 1;
				st[id] = st[id << 1] + st[id << 1 | 1];
			}
		}
		void build (int id, int l, int r) {
			if (l == r) {
				st[id] = Node();
				return;
			}
			int mid = l + r >> 1;
			build(id << 1, l, mid);
			build(id << 1 | 1, mid + 1, r);
			st[id] = st[id << 1] + st[id << 1 | 1];
		}
	} ST_PRE;

	struct SegmentTreeSuf {
		struct Node {
			int ans, len, pre;
			Node () {
				ans = 0;
				len = 1;
				pre = 0;
			}
		} st[4 * N];
		friend Node operator + (Node a, Node b) {
			Node res;
			res.pre = 1LL * a.pre * b.pre % MOD;
			res.len = a.len + b.len;
			res.ans = 1LL * a.ans * power2[b.len] % MOD + 1LL * b.ans * a.pre % MOD;
			return res;
		}
		void update (int pos, int val) {
			int id = 1, l = 1, r = n;
			while (l < r) {
				int mid = (l + r) >> 1;
				if (pos <= mid) id = id << 1, r = mid;
				else id = id << 1 | 1, l = mid + 1;
			}
			st[id].pre+= val;
			st[id].ans+= val;
			while (id > 1) {
				id >>= 1;
				st[id] = st[id << 1] + st[id << 1 | 1];
			}
		}
		void build (int id, int l, int r) {
			if (l == r) {
				st[id] = Node();
				return;
			}
			int mid = l + r >> 1;
			build(id << 1, l, mid);
			build(id << 1 | 1, mid + 1, r);
			st[id] = st[id << 1] + st[id << 1 | 1];
		}
	} ST_SUF;

	struct SegmentTreeMul {
		struct Node {
			int ans, pre, suf;
			Node () {
				ans = 0;
				pre = 0;
				suf = 0;
			}
		} st[4 * N];
		friend Node operator + (Node a, Node b) {
			Node res;
			res.pre = 1LL * a.pre * b.pre % MOD;
			res.suf = 1LL * a.suf * b.suf % MOD;
			res.ans = 1LL * a.ans * b.suf % MOD + 1LL * a.pre * b.ans % MOD;
			return res;
		}
		void update (int pos, int val) {
			int id = 1, l = 1, r = n;
			while (l < r) {
				int mid = (l + r) >> 1;
				if (pos <= mid) id = id << 1, r = mid;
				else id = id << 1 | 1, l = mid + 1;
			}
			st[id].pre+= val;
			st[id].ans+= val;
			st[id].suf+= val;
			while (id > 1) {
				id >>= 1;
				st[id] = st[id << 1] + st[id << 1 | 1];
			}
		}
	} ST_MUL;

	map <int, vector <int>> pos_val;

	void solve() {
		power2[0] = 1;
		for (int i = 1; i <= n; i++) {
			power2[i] = 1LL * power2[i - 1] * 2 % MOD;
		}
		map <int, int> mp;
		mp[0] = 1;
		for (int i = 1; i <= n; i++) {
			mp[a[i]] = 1;
			mp[b[i]] = 1;
			pos_val[a[i]].push_back(i);
			pos_val[b[i]].push_back(i);
		}	

		ST_PRE.build(1, 1, n);
		ST_SUF.build(1, 1, n);

		int ans = 0, last = - 1;

		for (auto x : mp) {
			if (last != - 1) {
				int diff = x.first - last;
				ans = (ans - 1LL * ST_PRE.st[1].ans * diff % MOD + MOD) % MOD;
				ans = (ans - 1LL * ST_SUF.st[1].ans * diff % MOD + MOD) % MOD;
				ans = (ans + 1LL * ST_MUL.st[1].ans * diff % MOD + MOD) % MOD;
			}
			for (int p : pos_val[x.first]) {
				ST_MUL.update(p, 1);
				ST_PRE.update(p, 1);
				ST_SUF.update(p, 1);
			}
			last = x.first;
		}

		for (int i = 1; i <= n; i++) {
	        ans = (ans + 1LL * power2[n - 1] * (last - a[i]) % MOD) % MOD;
	        ans = (ans + 1LL * power2[n - 1] * (last - b[i]) % MOD) % MOD;
	    }

	    cout << ans;
	}
}

void process(void) {
	// return sub1::solve();
	return sub2::solve();
}

signed main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	file("kieuoanh");
			
	int tc = 1; // cin >> tc;
	while (tc--) {
		init();
		process();
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:18:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:264:9: note: in expansion of macro 'file'
  264 |         file("kieuoanh");
      |         ^~~~
Main.cpp:18:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:264:9: note: in expansion of macro 'file'
  264 |         file("kieuoanh");
      |         ^~~~

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