이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 150010
#define DIMBUCKET 400
#include "elephants.h"
using namespace std;
int n,lg,nr_buckets,l,q,cnt,poz,val;
int what_bucket[DIM],x[DIM];
pair <int,int> v[DIM],aux[DIM],dp[DIMBUCKET][DIMBUCKET*2];
vector <pair<int,int> > buckets[DIMBUCKET];
void update_bucket (int bucket){
int el = 0;
for (auto it : buckets[bucket])
aux[++el] = it;
int j = el+1;
for (int i=el;i;i--){
while (aux[j-1].first > aux[i].first + l)
j--;
if (j <= el){
dp[bucket][i].first = dp[bucket][j].first + 1;
dp[bucket][i].second = dp[bucket][j].second;
} else {
dp[bucket][i].first = 1;
dp[bucket][i].second = aux[i].first + l;
}
}
}
void build (int x[]){
lg = n / sqrt (n); /// lungime bucket
for (int i=1;i<=n;i++){
v[i].first = x[i-1];
v[i].second = i;
}
sort (v+1,v+n+1);
for (int i=1;i<=n;i++){
what_bucket[v[i].second] = i / lg;
if (i % lg)
what_bucket[v[i].second]++;
buckets[what_bucket[v[i].second]].push_back(v[i]);
}
nr_buckets = n / lg;
if (n % lg)
nr_buckets++;
for (int i=1;i<=nr_buckets;i++)
sort (buckets[i].begin(),buckets[i].end());
/// dp[bucket][i] - nr min de intervale cu care pot sa acopar toate punctele
/// din bucketul asta, incepand de la al i - lea, si care e cea mai din dreapta poz
/// pt care pot sa fac asta
for (int i=1;i<=nr_buckets;i++){
update_bucket(i);
}
}
int query (){
int i = 1, val = -1, poz, sol = 0;
while (i <= nr_buckets){
if (buckets[i].empty()){
i++;
continue;
}
if (val == -1){
sol += dp[i][1].first;
val = dp[i][1].second;
i++;
} else {
if (buckets[i][ buckets[i].size()-1 ].first <= val)
i++;
else {
/// caut binar pe primul > val
int st = 1, dr = buckets[i].size(), sol_poz = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[i][mid-1].first > val){
sol_poz = mid;
dr = mid-1;
} else st = mid+1;
}
sol += dp[i][sol_poz].first;
val = dp[i][sol_poz].second;
i++;
}
}
}
/*int poz = 1, sol = 0;
for (int i=1;i<=nr_buckets;i++){
if (!buckets[i].size())
continue;
sol += dp[i][poz].first;
int val = dp[i][poz].second;
/// trb sa vad care e noul poz in urmatorul bucket
/// daca sar peste mai multe bucketuri ce fac?
while (i < nr_buckets && buckets[i+1][ buckets[i+1].size() -1].first <= val)
i++;
if (i + 1 > nr_buckets)
break;
int st = 1, dr = buckets[i+1].size(), sol_poz = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[i+1][mid-1].first >= val){
sol_poz = mid;
dr = mid-1;
} else st = mid+1;
}
poz = sol_poz;
}
*/
return sol;
}
void init (int _n, int _l, int v[]){
n = _n, l = _l;
build (v);
}
void sterge (int idx, int poz){
int i;
for (i=0;i<buckets[idx].size();i++)
if (buckets[idx][i] == v[poz])
break;
for (int j=i+1;j<buckets[idx].size();j++)
buckets[idx][j-1] = buckets[idx][j];
buckets[idx].pop_back();
}
void adauga (int idx, int poz){
int i;
for (i=0;i<buckets[idx].size();i++)
if (v[poz].first <= buckets[idx][i].first)
break;
buckets[idx].push_back(make_pair(0,0));
for (int j=buckets[idx].size()-1;j>i;j--)
buckets[idx][j] = buckets[idx][j-1];
buckets[idx][i] = v[poz];
}
int update (int poz, int val){
cnt++;
///if (cnt == lg) /// refac bucketurile
/// build();
poz++;
int idx = what_bucket[poz];
sterge (idx,poz);
//buckets[idx].erase(make_pair(v[poz].first,poz));
update_bucket (idx);
/// trb sa vad in ce bucket l as pune
v[poz].first = val;
int st = 1, dr = nr_buckets, sol = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[mid][0].first <= val){
sol = mid;
st = mid+1;
} else dr = mid-1;
}
what_bucket[poz] = sol;
adauga(sol,poz);
//buckets[sol].insert(v[poz]);
update_bucket(sol);
return query();
}
/*
int main (){
ifstream cin ("date.in");
ofstream cout ("date.out");
cin>>n>>l>>q;
for (int i=0;i<n;i++)
cin>>x[i];
init(n,l,x);
//cin>>q;
for (;q--;){
int useless;
cin>>poz>>val>>useless;
cout<<update (poz,val)<<"\n";
}
return 0;
}
*/
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'int query()':
elephants.cpp:77:26: warning: unused variable 'poz' [-Wunused-variable]
77 | int i = 1, val = -1, poz, sol = 0;
| ^~~
elephants.cpp: In function 'void sterge(int, int)':
elephants.cpp:162:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (i=0;i<buckets[idx].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:166:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for (int j=i+1;j<buckets[idx].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void adauga(int, int)':
elephants.cpp:174:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (i=0;i<buckets[idx].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
# | 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... |