# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
424492 | zoooma13 | Financial Report (JOI21_financial) | C++14 | 799 ms | 45972 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct pref : set <pair<int ,int>>{
void add(int i ,int v){
auto it = insert({i ,v}).first;
if(it != begin() && prev(it)->second >= it->second){
erase(it);
return;
}
while(next(it) != end() && next(it)->second <= it->second)
erase(next(it));
}
int qry(int i){
auto it = upper_bound({i ,-1});
if(it == begin())
return 0;
return prev(it)->second;
}
};
vector <int> par;
vector <pref> trac;
int fnd(int u){
return par[u] == u? u : par[u] = fnd(par[u]);
}
int unn(int u ,int v){
u = fnd(u) ,v = fnd(v);
if(u == v)
return v;
if(trac[u].size() > trac[v].size())
swap(u ,v);
par[u] = v;
for(auto s : trac[u])
trac[v].add(s.first ,s.second);
trac[u].clear();
return v;
}
int main()
{
int n ,d;
scanf("%d%d",&n,&d);
vector <int> a(n);
for(int&i : a)
scanf("%d",&i);
vector <int> ord;
for(int i = 0; i < n; i++){
ord.push_back(i);
par.push_back(i);
trac.push_back({});
trac.back().add(i ,1);
}
sort(ord.begin() ,ord.end() ,[&](int&i ,int&j){
return a[i] == a[j]? i > j : a[i] < a[j];
});
set <int> added;
for(int&i : ord){
auto it = added.insert(i).first;
if(it != added.begin() && i - *prev(it) <= d){
trac[i].clear();
par[i] = fnd(*prev(it));
trac[par[i]].add(i ,trac[par[i]].qry(i)+1);
}
if(next(it) != added.end() && *next(it) - i <= d)
unn(i ,*next(it));
}
printf("%d\n",trac[fnd(0)].qry(n));
}
컴파일 시 표준 에러 (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... |