제출 #1070281

#제출 시각아이디문제언어결과실행 시간메모리
1070281underwaterkillerwhaleFlooding Wall (BOI24_wall)C++17
58 / 100
4030 ms565748 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 + 2; const int Mod = 1e9 + 7; const ll INF = 1e18 + 7; const ll BASE = 137; const int szBL = 320; int n, m; int a[2][(int)5e5 + 7]; int sval[2 * N]; int vals[2 * N] = {0}; inline void add (int &a, int b) { a = a + b; if (a >= Mod) a-= Mod; } namespace sub5 { int dp[2][5], f[(int)5e5 + 7][5]; void solution () { rep (i, 1, n) rep (k, 0, 1) a[k][i] = lower_bound(vals, vals + m, a[k][i]) - vals + 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]) { add(f[i][a[k][i]], f[i + 1][j]); } else { add(f[i][j], f[i + 1][j]); } } } int res = 0; rep (i, 1, n) { rep (k, 0, 1) { 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) { add(res, 1LL * dp[i&1^1][j] * sval[j] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod); } 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) { add(res, 1LL * f[i + 1][j] * sval[j + 1] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod); } } rep (j, 1, m) dp[i&1][j] = 0; rep (k, 0, 1) { rep (j, 1, m) { if (j <= a[k][i]) { add(dp[i & 1][a[k][i]], dp[i&1^1][j]); } else { add(dp[i & 1][j], dp[i&1^1][j]); } } } } cout << res<<"\n"; } } int dp[2][2 * N]; int f[N][2 * N]; 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[m++] = a[1][i]; vals[m++] = a[0][i]; } sort (vals, vals + m); m = unique(vals, vals + m) - vals; rep (i, 1, n) rep (k, 0, 1) a[k][i] = lower_bound(vals, vals + m, a[k][i]) - vals + 1; if (m <= 3) { sub5 :: solution(); return; } 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]) { add(f[i][a[k][i]], f[i + 1][j]); } else { add(f[i][j], f[i + 1][j]); } } } int res = 0; rep (i, 1, n) { rep (k, 0, 1) { 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) { add(res, 1LL * dp[i&1^1][j] * sval[j] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod); } 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) { add(res, 1LL * f[i + 1][j] * sval[j + 1] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod); } } rep (j, 1, m) dp[i&1][j] = 0; rep (k, 0, 1) { rep (j, 1, m) { if (j <= a[k][i]) { add(dp[i & 1][a[k][i]], dp[i&1^1][j]); } else { add(dp[i & 1][j], dp[i&1^1][j]); } } } } 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 */

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void sub5::solution()':
Main.cpp:70:40: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   70 |                     add(res, 1LL * dp[i&1^1][j] * sval[j] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod);
      |                                       ~^~
Main.cpp:74:50: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   74 |                     sval[j] = (sval[j + 1] + dp[i&1^1][j]) % Mod;
      |                                                 ~^~
Main.cpp:84:53: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   84 |                         add(dp[i & 1][a[k][i]], dp[i&1^1][j]);
      |                                                    ~^~
Main.cpp:87:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   87 |                         add(dp[i & 1][j], dp[i&1^1][j]);
      |                                              ~^~
Main.cpp: In function 'void solution()':
Main.cpp:143:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  143 |                 add(res, 1LL * dp[i&1^1][j] * sval[j] % Mod * (vals[j - 1] - vals[a[k][i] - 1]) % Mod);
      |                                   ~^~
Main.cpp:147:46: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  147 |                 sval[j] = (sval[j + 1] + dp[i&1^1][j]) % Mod;
      |                                             ~^~
Main.cpp:157:49: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  157 |                     add(dp[i & 1][a[k][i]], dp[i&1^1][j]);
      |                                                ~^~
Main.cpp:160:43: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  160 |                     add(dp[i & 1][j], dp[i&1^1][j]);
      |                                          ~^~
#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...