제출 #398476

#제출 시각아이디문제언어결과실행 시간메모리
398476model_codeThe short shank; Redemption (BOI21_prison)C++17
100 / 100
632 ms213652 KiB
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int main() { int N, D, T; scanf("%d %d %d", &N, &D, &T); int last_rebel = -1; int num_rebels = 0; vector<int> inactive(N, -1); vector<int> times(N); vector<int> next; stack<pii> S; for(int i = 0; i < N; ++i) { int t; scanf("%d", &t); times[i] = t; last_rebel = max(last_rebel, i + T - t); if(not S.empty()) S.top().second = max(S.top().second, i + T - t); if(t > T and last_rebel >= i) { int last_rebel_internal = -1; ++num_rebels; while(not S.empty()) { pii curr = S.top(); int j = curr.first; last_rebel_internal = max(last_rebel_internal, curr.second); if(last_rebel_internal >= i) break; next[inactive[j]] = next.size(); S.pop(); } S.emplace(i, -1); inactive[i] = next.size(); next.push_back(-1); } if(t <= T) ++num_rebels; } vector<vector<int>> children(next.size()); vector<int> subtree_height(next.size(), 1); vector<int> max_subtree(next.size(), -1); vector<vector<int>> PQpre(next.size() + 1); deque<pii> PQ; vector<char> erased(next.size(), false); for(int i = 0; i < next.size(); ++i) { int j = next[i]; if(j != -1) { children[j].push_back(i); int new_height = subtree_height[i] + 1; if(new_height > subtree_height[j]) { subtree_height[j] = new_height; max_subtree[j] = children[j].size() - 1; } } PQpre[subtree_height[i]].push_back(i); } for(int i = PQpre.size() - 1; i >= 0; --i) for(int x : PQpre[i]) PQ.emplace_back(i, x); int stopped = 0; for(int i = 0; i < D and not PQ.empty(); ++i) { pii curr = PQ.front(); PQ.pop_front(); stopped += curr.first; int j; for(j = curr.second; max_subtree[j] != -1 and not erased[j]; j = children[j][max_subtree[j]]) erased[j] = true; erased[j] = true; while(not PQ.empty() and erased[PQ.front().second]) PQ.pop_front(); } printf("%d\n", num_rebels - stopped); return 0; }

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

prison.cpp: In function 'int main()':
prison.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < next.size(); ++i)
      |                    ~~^~~~~~~~~~~~~
prison.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     int N, D, T; scanf("%d %d %d", &N, &D, &T);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |         int t; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~
#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...