제출 #828905

#제출 시각아이디문제언어결과실행 시간메모리
828905QwertyPiThe short shank; Redemption (BOI21_prison)C++14
0 / 100
20 ms47316 KiB
#include <bits/stdc++.h> #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") using namespace std; const int N = 2e6 + 11; int a[N]; int ps[N]; vector<int> rm[N]; struct range{ int l, r; }; struct SegTree{ int t[1 << 22], lz[1 << 22]; void push(int v){ if(lz[v]){ lz[v * 2 + 1] += lz[v]; lz[v * 2 + 2] += lz[v]; t[v * 2 + 1] += lz[v]; t[v * 2 + 2] += lz[v]; lz[v] = 0; } } void init(int v, int l, int r){ if(l == r) t[v] = (1 << 30), lz[v] = 0; else { int m = (l + r) / 2; init(v * 2 + 1, l, m); init(v * 2 + 2, m + 1, r); t[v] = 1 << 30, lz[v] = 0; } } void range_add(int ql, int qr, int qv, int v, int l, int r){ if(qr < l || r < ql) return; if(ql <= l && r <= qr) t[v] += qv, lz[v] += qv; else { push(v); int m = (l + r) / 2; range_add(ql, qr, qv, v * 2 + 1, l, m); range_add(ql, qr, qv, v * 2 + 2, m + 1, r); t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); } } int range_min(){ return t[0]; } void point_update(int qi, int qv, int v, int l, int r){ if(l == r) t[v] = qv; else { push(v); int m = (l + r) / 2; if(qi <= m) point_update(qi, qv, v * 2 + 1, l, m); else point_update(qi, qv, v * 2 + 2, m + 1, r); t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); } } } ST; int dp[501][501]; int32_t main(){ cin.tie(0); cout.tie(0)->sync_with_stdio(false); int n, d, t; cin >> n >> d >> t; for(int i = 0; i < n; i++){ cin >> a[i]; a[i] = max(0, t - a[i] + 1); } for(int i = 0; i < n; i++){ if(a[i] == 0) a[i] = -1; else a[i] = min(n, i + a[i]), rm[a[i]].push_back(i); } priority_queue<int> pq1, pq2; vector<range> R; int ans = 0; for(int i = 0; i < n; i++){ for(auto j : rm[i]) pq2.push(j); while(pq1.size() && pq2.size() && pq1.top() == pq2.top()) pq1.pop(), pq2.pop(); if(a[i] == -1){ if(!pq1.empty()) R.push_back({pq1.top(), i - 1}), ans++; }else{ pq1.push(i); ans++; } } for(auto [l, r] : R){ ps[r]++; } for(int i = 0; i < n - 1; i++){ ps[i + 1] += ps[i]; } sort(R.begin(), R.end(), [](range a, range b){ return a.r < b.r; }); for(int i = 0; i < d; i++){ int ri = 0; ST.init(0, 0, n - 1); for(int j = 0; j < n; j++){ while(ri < R.size() && R[ri].r < j) ST.range_add(0, R[ri].l - 1, 1, 0, 0, n - 1), ri++; dp[i + 1][j] = ST.range_min(); ST.point_update(j, dp[i][j], 0, 0, n - 1); } } int mx = 0; for(int i = 0; i < n; i++){ mx = max(mx, ps[i] - dp[d][i]); } cout << ans - mx << endl; }

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

prison.cpp: In function 'int32_t main()':
prison.cpp:90:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |  for(auto [l, r] : R){
      |           ^
prison.cpp:104:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    while(ri < R.size() && R[ri].r < j) ST.range_add(0, R[ri].l - 1, 1, 0, 0, n - 1), ri++;
      |          ~~~^~~~~~~~~~
#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...