# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
398476 | model_code | The short shank; Redemption (BOI21_prison) | C++17 | 632 ms | 213652 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |