제출 #753241

#제출 시각아이디문제언어결과실행 시간메모리
753241OlympiaK개의 묶음 (IZhO14_blocks)C++17
53 / 100
2 ms1108 KiB
#include <vector> #include <iostream> #include <cassert> #include <cmath> #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <map> #include <set> using namespace std; vector<int64_t> p; //const int MX = 131072; const int MX = 300; struct SegmentTree { int64_t orig[2 * MX]; int64_t vec[2 * MX]; int64_t lazy[2 * MX]; const int64_t INF = 1e18; void push (int dum) { if (lazy[dum] == -1) { return; } lazy[2 * dum + 1] = lazy[dum]; lazy[2 * dum + 2] = lazy[dum]; vec[2 * dum + 1] = lazy[dum] + orig[2 * dum + 1]; vec[2 * dum + 2] = lazy[dum] + orig[2 * dum + 2]; lazy[dum] = -1; } void upd (int dum, int tl, int tr, int l, int r, int64_t x) { if (tl >= l and tr <= r) { lazy[dum] = x; vec[dum] = orig[dum] + x; return; } if (tl > r or l > tr) { return; } push(dum); upd(2 * dum + 1, tl, (tl + tr)/2, l, r, x); upd(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r, x); vec[dum] = min(vec[2 * dum + 1], vec[2 * dum + 2]); } int64_t query (int dum, int tl, int tr, int l, int r) { if (tl >= l and tr <= r) { return vec[dum]; } if (tl > r or l > tr) { return INF; } push(dum); return min(query(2 * dum + 1, tl, (tl + tr)/2, l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r)); } void upd (int l, int r, int64_t x) { upd(0, 0, (int)p.size() - 1, l, r, x); } int64_t query (int l, int r) { return query(0, 0, (int)p.size() - 1, l, r); } void build (int dum, int tl, int tr) { if (tl == tr) { orig[dum] = p[tl]; return; } build(2 * dum + 1, tl, (tl + tr)/2); build(2 * dum + 2, (tl + tr)/2 + 1, tr); orig[dum] = min(orig[2 * dum + 1], orig[2 * dum + 2]); } void reset () { for (int i = 0; i < 2 * p.size(); i++) { orig[i] = 0, lazy[i] = -1; } build(0, 0, (int)p.size() - 1); for (int i = 0; i < 2 * p.size(); i++) { vec[i] = orig[i]; } } SegmentTree () { int n = p.size(); for (int i = 0; i < 2 * n; i++) { orig[i] = 0; lazy[i] = -1; } build(0, 0, n - 1); for (int i = 0; i < 2 * n; i++) { vec[i] = orig[i]; } } }; struct SparseTable { int64_t dp[MX][18]; int64_t query (int l, int r) { int sz = log2(r - l + 1); return min(dp[l][sz], dp[r - (1 << sz) + 1][sz]); } void upd (vector<int64_t> &a) { for (int j = 0; j < 18; j++) { for (int i = 0; i < a.size(); i++) { if (j == 0) { dp[i][j] = a[i]; } else { dp[i][j] = min(dp[i][j - 1], dp[min(i + (1 << (j - 1)), (int)a.size() - 1)][j - 1]); } } } } }; int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, K; cin >> N >> K; vector<int64_t> arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } int64_t INF = 1e17; vector<int64_t> cur(N + 1); p.assign(N + 1, INF), cur.assign(N + 1, INF); for (int j = 1; j <= N; j++) { p[j] = ((j == 1) ? arr[0] : max(p[j - 1], arr[j - 1])); } for (int i = 0; i < arr.size(); i++) { arr[i] = -arr[i]; } SparseTable st_a; st_a.upd(arr); for (int i = 0; i < arr.size(); i++) { arr[i] = -arr[i]; } int nxt[N]; for (int j = 0; j < N; j++) { int l = 0; int r = j; while (l != r) { int m = (l + r)/2; if (st_a.query(m, j) == -arr[j]) { r = m; } else { l = m + 1; } } nxt[j] = l; } while (__builtin_popcount(p.size()) != 1) { p.push_back(0); cur.push_back(0); } SparseTable st_p; SegmentTree val; for (int i = 2; i <= K; i++) { val.reset(); st_p.upd(p); for (int j = 1; j <= N; j++) { if (j == 1) { cur[j] = p[0] + arr[0]; } else { cur[j] = INF; int ind = nxt[j - 1]; val.upd(ind, j - 1, arr[j - 1]); cur[j] = min(val.query(0, ind - 1), arr[j - 1] + st_p.query(ind, j - 1)); } } swap(cur, p); if (p == cur) { break; } } cout << p[N]; }

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

blocks.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
blocks.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
blocks.cpp: In member function 'void SegmentTree::reset()':
blocks.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = 0; i < 2 * p.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
blocks.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < 2 * p.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
blocks.cpp: In member function 'void SparseTable::upd(std::vector<long int>&)':
blocks.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int i = 0; i < a.size(); i++) {
      |                             ~~^~~~~~~~~~
blocks.cpp: In function 'int main()':
blocks.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < arr.size(); i++) {
      |                     ~~^~~~~~~~~~~~
blocks.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < arr.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...