제출 #961274

#제출 시각아이디문제언어결과실행 시간메모리
961274BhavayGoyalGroup Photo (JOI21_ho_t3)C++14
100 / 100
376 ms600 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define ld long double #define ar array #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define all(x) x.begin(), x.end() #define f first #define s second #define endl "\n" const int MOD = 1e9+7; const int inf = 1e9; const ll linf = 1e18; const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1}; const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // -------------------------------------------------- Main Code -------------------------------------------------- struct bits { int n; vi tree; bits(int N) {n = N+5; tree = vi(n+5);} void update(int idx, int val) { for (idx; idx <= n; idx += (idx&-idx)) tree[idx] += val; } int sum(int idx) { int ans = 0; for (idx; idx; idx -= (idx&-idx)) ans += tree[idx]; return ans; } int query(int l, int r) { return sum(r)-sum(l-1); } }; const int N = 5001; int a[N], pos[N], dp[N]; void sol() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i; for (int i = 1; i <= n; i++) dp[i] = inf; bits smaller(n+1); vi small(n+1); for (int i = 1; i <= n; i++) { smaller.update(pos[i], 1); int cost = 0; bits bigger(n); for (int j = i; j >= 1; j--) { // cost = (elements < j after pos[j]) + (elements > j && <= i after pos[j]) if (i == j) small[i] = smaller.query(pos[j]+1, n); cost += small[j]; cost += bigger.query(pos[j]+1, n); cost -= bigger.query(1, pos[j]-1); dp[i] = min(dp[j-1]+cost, dp[i]); bigger.update(pos[j], 1); } } cout << dp[n] << endl; } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } return 0; }

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

Main.cpp: In member function 'void bits::update(int, int)':
Main.cpp:41:42: warning: statement has no effect [-Wunused-value]
   41 |     void update(int idx, int val) { for (idx; idx <= n; idx += (idx&-idx)) tree[idx] += val; }
      |                                          ^~~
Main.cpp: In member function 'int bits::sum(int)':
Main.cpp:42:42: warning: statement has no effect [-Wunused-value]
   42 |     int sum(int idx) { int ans = 0; for (idx; idx; idx -= (idx&-idx)) ans += tree[idx]; return ans; }
      |                                          ^~~
#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...