Submission #895357

#TimeUsernameProblemLanguageResultExecution timeMemory
895357IrateMoney (IZhO17_money)C++14
0 / 100
1 ms4188 KiB
#include<bits/stdc++.h> using namespace std; int n; vector<int>v; struct SegmentTree{ vector<pair<int, int>>sTree; void init(int n){ sTree.resize(4 * n); } void Build(int node, int l, int r, vector<int>&v){ if(l == r){ sTree[node] = {v[l], v[l]}; } else{ int mid = (l + r) >> 1; Build(node * 2, l, mid, v); Build(node * 2 + 1, mid + 1, r, v); sTree[node] = {min(sTree[node * 2].first, sTree[node * 2 + 1].first), max(sTree[node * 2].second, sTree[node * 2 + 1].second)}; } } int Min_Query(int node, int l, int r, int ql, int qr){ if(ql <= l && r <= qr){ return sTree[node].first; } if(ql > r || l > qr)return 1e9; int mid = (l + r) >> 1; int lc = Min_Query(node * 2, l, mid, ql, qr); int rc = Min_Query(node * 2 + 1, mid + 1, r, ql, qr); return min(lc, rc); } int Max_Query(int node, int l, int r, int ql, int qr){ if(ql <= l && r <= qr){ return sTree[node].second; } if(ql > r || l > qr)return 0; int mid = (l + r) >> 1; int lc = Max_Query(node * 2, l, mid, ql, qr); int rc = Max_Query(node * 2 + 1, mid + 1, r, ql, qr); return max(lc, rc); } }; struct MergeSortTree{ vector<vector<int>>mTree; void init(int n){ mTree.resize(4 * n); } vector<int> Merge(vector<int>&left, vector<int>&right){ vector<int>res; int p1 = 0, p2 = 0; while(p1 < left.size() || p2 < right.size()){ if(p1 == left.size()){ res.push_back(right[p2++]); } else if(p2 == right.size()){ res.push_back(left[p1++]); } else if(left[p1] > right[p2]){ res.push_back(right[p2++]); } else{ res.push_back(left[p1++]); } } return res; } void Build(int node, int l, int r, vector<int>&v){ if(l == r){ mTree[node].push_back(v[l]); } else{ int mid = (l + r) >> 1; Build(node * 2, l, mid, v); Build(node * 2 + 1, mid + 1, r, v); mTree[node] = Merge(mTree[node * 2], mTree[node * 2 + 1]); } } int Query(int node, int l, int r, int ql, int qr, int num1, int num2){ if(ql <= l && r <= qr){ auto itr1 = upper_bound(mTree[node].begin(), mTree[node].end(), num1); auto itr2 = lower_bound(mTree[node].begin(), mTree[node].end(), num2); itr2--; int pos1 = itr1 - mTree[node].begin(); int pos2 = itr2 - mTree[node].begin(); return max(0, pos2 - pos1 + 1); } if(ql > r || l > qr)return 0; int mid = (l + r) >> 1; int lc = Query(node * 2, l, mid, ql, qr, num1, num2); int rc = Query(node * 2 + 1, mid + 1, r, ql, qr, num1, num2); return lc + rc; } }; SegmentTree tree; MergeSortTree mtree; /* 6 3 6 4 5 1 2 */ const int mxN = 1e6 + 6; int dp[mxN]; int rec(int indx){ int res = 1e9, mn = 1e9, mx = 0; if(indx == n + 1)return 0; if(dp[indx] != -1)return dp[indx]; for(int i = indx;i <= n;++i){ mn = min(mn, v[i]); mx = max(mx, v[i]); int MN = tree.Min_Query(1, 1, n, 1, indx - 1), MX = tree.Max_Query(1, 1, n, 1, indx - 1); int cnt = mtree.Query(1, 1, n, 1, indx - 1, mn, mx); if(mn > MX || MN > mx || cnt == 0)res = min(res, rec(i + 1) + 1); else break; } return dp[indx] = res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; v.resize(n + 1); tree.init(n); mtree.init(n); for(int i = 1;i <= n;++i){ cin >> v[i]; } for(int i = 0;i < mxN;++i){ dp[i] = -1; } tree.Build(1, 1, n, v); mtree.Build(1, 1, n, v); int res = 1e9; for(int i = 1;i <= n;++i){ if(v[i] < v[i - 1])break; res = min(res, rec(i + 1) + 1); } cout << res; }

Compilation message (stderr)

money.cpp: In member function 'std::vector<int> MergeSortTree::Merge(std::vector<int>&, std::vector<int>&)':
money.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while(p1 < left.size() || p2 < right.size()){
      |               ~~~^~~~~~~~~~~~~
money.cpp:50:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while(p1 < left.size() || p2 < right.size()){
      |                                   ~~~^~~~~~~~~~~~~~
money.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if(p1 == left.size()){
      |                ~~~^~~~~~~~~~~~~~
money.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             else if(p2 == right.size()){
      |                     ~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...