Submission #1274737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274737		Bui_Quoc_Cuong	Flooding Wall (BOI24_wall)	C++20	20 / 100	60 ms	14264 KiB

Main

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

#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;
		}

		int ans = 0;
		pref[0] = 1;
		suf[n + 1] = 1;
		
		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;
				(cnt+= sum) %= MOD;
			}
			(ans+= 1LL * cnt * (values[it] - values[it - 1]) % MOD) %= MOD;
		}	

		cout << ans;
	}
}

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

int 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:98:9: note: in expansion of macro 'file'
   98 |         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:98:9: note: in expansion of macro 'file'
   98 |         file("kieuoanh");
      |         ^~~~

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