Submission #1274383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274383		Bui_Quoc_Cuong	Flooding Wall (BOI24_wall)	C++20	44 / 100	561 ms	1114112 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 MAXN = 5e5 + 5;
const int MOD = 1e9 + 7;

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

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 {	
	void add (int &x, const int y) {
		x+= y;
		if (x >= MOD) x-= MOD;
	}

	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());
		for (int i = 1; i <= n; i++) {
			a[i] = upper_bound(ALL(values), a[i]) - values.begin();
			b[i] = upper_bound(ALL(values), b[i]) - values.begin();
		}
		int LIM = sz(values);
		vector <vector <int>> dpLeft, dpRight;
		dpLeft.resize(n + 2, vector <int> (LIM + 3, 0));
		dpRight.resize(n + 2, vector <int> (LIM + 3, 0));	
		dpLeft[0][0] = 1;
		for (int i = 0; i < n; ++i) for (int j = 0; j <= LIM; j++) if (dpLeft[i][j] > 0) {
			(dpLeft[i + 1][max(j, a[i + 1])]+= dpLeft[i][j]) %= MOD;
			(dpLeft[i + 1][max(j, b[i + 1])]+= dpLeft[i][j]) %= MOD;
		}
		dpRight[n + 1][0] = 1;
		for (int i = n + 1; i > 1; i--) for (int j = 0; j <= LIM; j++) if (dpRight[i][j] > 0) {
			(dpRight[i - 1][max(j, a[i - 1])]+= dpRight[i][j]) %= MOD;
			(dpRight[i - 1][max(j, b[i - 1])]+= dpRight[i][j]) %= MOD;
		}
		int ans = 0;
		vector <int> concac;
		concac.resize(LIM + 3, 0);
		vector <int> cailon;
		cailon.resize(LIM + 3, 0);
		for (int i = 2; i <= n - 1; i++) {
			for (int j = 1; j <= LIM; j++) {
				concac[j] = 0;
				(concac[j]+= concac[j - 1]) %= MOD;
				(concac[j]+= dpLeft[i - 1][j]) %= MOD;
			}	
			// a[i]
			for (int j = a[i]; j <= LIM; j++) {
				int cnt_way = 1LL * dpRight[i + 1][j] * ((concac[LIM] - concac[j - 1] + MOD) % MOD) % MOD;
				add(ans, 1LL * cnt_way * (values[j - 1] - values[a[i] - 1]) % MOD);
			}
			// b[i]
			for (int j = b[i]; j <= LIM; j++) {
				int cnt_way = 1LL * dpRight[i + 1][j] * ((concac[LIM] - concac[j - 1] + MOD) % MOD) % MOD;
				add(ans, 1LL * cnt_way * (values[j - 1] - values[b[i] - 1]) % MOD);
			}
			for (int j = 1; j <= LIM; j++) {
				cailon[j] = 0;
				(cailon[j]+= cailon[j - 1]) %= MOD;
				(cailon[j]+= dpRight[i + 1][j]) %= MOD;
			}
			// a[i]
			for (int j = a[i]; j <= LIM; j++) {
				int cnt_way = 1LL * dpLeft[i - 1][j] * ((cailon[LIM] - cailon[j] + MOD) % MOD) % MOD;
				add(ans, 1LL * cnt_way * (values[j - 1] - values[a[i] - 1]) % MOD);
			}
			// b[i]
			for (int j = b[i]; j <= LIM; j++) {
				int cnt_way = 1LL * dpLeft[i - 1][j] * ((cailon[LIM] - cailon[j] + MOD) % MOD) % MOD;
				add(ans, 1LL * cnt_way * (values[j - 1] - values[b[i] - 1]) % MOD);
			}
		}
		cout << ans;
	}
}

namespace sub2 {

	void solve() {

	}
}

void process(void) {
	sub1::solve();
	sub2::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:135:5: note: in expansion of macro 'file'
  135 |     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:135:5: note: in expansion of macro 'file'
  135 |     file("kieuoanh");
      |     ^~~~

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