Submission #1070252

#TimeUsernameProblemLanguageResultExecution timeMemory
1070252underwaterkillerwhaleFlooding Wall (BOI24_wall)C++17
44 / 100
5046 ms560720 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e4 + 7; const int Mod = 1e9 + 7; const ll INF = 1e18 + 7; const ll BASE = 137; const int szBL = 320; int n, m; int a[2][N]; int dp[2][2 * N]; int f[N][2 * N]; ll sval[2 * N]; vector<int> vals = {0}; void solution () { cin >> n; rep (i, 1, n) cin >> a[0][i]; rep (i, 1, n) { cin >> a[1][i]; if (a[1][i] <= a[0][i]) swap(a[1][i], a[0][i]); vals.pb(a[1][i]); vals.pb(a[0][i]); } sort (ALL(vals)); vals.resize(m = unique(ALL(vals)) - vals.begin()); rep (i, 1, n) rep (k, 0, 1) a[k][i] = lower_bound(ALL(vals), a[k][i]) - vals.begin() + 1; dp[0][1] = 1; dp[0][1] = 1; f[n + 1][1] = 1; f[n + 1][1] = 1; reb (i, n, 1) rep (k, 0, 1) { rep (j, 1, m) { if (j <= a[k][i]) { (f[i][a[k][i]] += f[i + 1][j]) %= Mod; } else { (f[i][j] += f[i + 1][j])%= Mod; } } } ll res = 0; rep (i, 1, n) { rep (k, 0, 1) { // cout << i<<" "<<a[k][i] <<"\n"; sval[m + 1] = 0; reb (j, m, a[k][i] + 1) { sval[j] = (sval[j + 1] + f[i + 1][j]) % Mod; } rep (j, a[k][i] + 1, m) { (res += 1LL * dp[i&1^1][j] * sval[j] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod) %= Mod; // cout << i<<" "<<j<<" "<<p<<" "<<j<<" "<<a[k][i] <<" a\n"; } sval[m + 1] = 0; reb (j, m, a[k][i] + 1) { sval[j] = (sval[j + 1] + dp[i&1^1][j]) % Mod; } rep (j, a[k][i] + 1, m) { (res += 1LL * f[i + 1][j] * sval[j + 1] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod) %= Mod; // cout << i<<" "<<j<<" "<<p<<" "<<j<<" "<<a[k][i] <<" a\n"; } } rep (j, 1, m) dp[i&1][j] = 0; rep (k, 0, 1) { rep (j, 1, m) { if (j <= a[k][i]) { (dp[i & 1][a[k][i]] += dp[i&1^1][j]) %= Mod; } else { (dp[i & 1][j] += dp[i&1^1][j]) %= Mod; } } } } cout << res<<"\n"; } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +4 mình có muốn dùng mảng này không? 2 + 8 * 2 - 9 4 1 1 1 1 2 2 2 2 */

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:75:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   75 |                 (res += 1LL * dp[i&1^1][j] * sval[j] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod) %= Mod;
      |                                  ~^~
Main.cpp:80:46: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   80 |                 sval[j] = (sval[j + 1] + dp[i&1^1][j]) % Mod;
      |                                             ~^~
Main.cpp:91:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   91 |                     (dp[i & 1][a[k][i]] += dp[i&1^1][j]) %= Mod;
      |                                               ~^~
Main.cpp:94:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   94 |                     (dp[i & 1][j] += dp[i&1^1][j]) %= Mod;
      |                                         ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...