이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN = 150000;
int N, L;
v<int> E;
void init(int n, int l, int X[])
{
N = n;
L = l;
for(int i=0; i<N; i++) E.push_back(X[i]);
}
const int BUCK = 400;
int qNum = 0;
v<int> buckInd(MAXN);
v<v<ii>> bucks(MAXN/BUCK + 1);
v<v<ii>> bucksAns(MAXN/BUCK+1);
void rebuildBuck(int b){
bucksAns[b].resize(bucks[b].size(), {0,0});
for(int i=bucks[b].size()-1; i>=0; i--){
auto it = lower_bound(bucks[b].begin()+i+1, bucks[b].end(), make_pair(bucks[b][i].fi+L+1, -1));
if(it==bucks[b].end()) bucksAns[b][i] = {1, bucks[b][i].fi+L+1};
else{
ii tmp = bucksAns[b][distance(bucks[b].begin(), it)];
bucksAns[b][i] = {1 + tmp.fi, tmp.se};
}
}
}
void rebuild(){
v<ii> e;
for(int i=0; i<N; i++) e.push_back({E[i], i});
sort(e.begin(), e.end());
for(int i=0; i<bucks.size(); i++) bucks[i].clear();
int b=0;
for(auto it:e){
if(bucks[b].size()==BUCK) b++;
bucks[b].push_back(it);
buckInd[it.se] = b;
}
for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
}
void move(int e, int x){
int b = buckInd[e];
bucks[b].erase(find(bucks[b].begin(), bucks[b].end(), make_pair(E[e], e)));
rebuildBuck(b);
E[e] = x;
int l=0, r=bucks.size()-1;
while(l<r){
int m=(l+r+1)/2;
if(bucks[m].size()>0 && bucks[m][0].fi<=x) l=m;
else r=m-1;
}
auto it = upper_bound(bucks[l].begin(), bucks[l].end(), make_pair(x, e));
bucks[l].insert(it, {x, e});
buckInd[e] = l;
rebuildBuck(l);
}
int ans(){
int cur = 0;
int ret = 0;
for(int b=0; b<bucks.size(); b++){
auto it = lower_bound(bucks[b].begin(), bucks[b].end(), make_pair(cur, -1));
if(it!=bucks[b].end()){
int i = distance(bucks[b].begin(), it);
ret += bucksAns[b][i].fi;
cur = bucksAns[b][i].se;
}
}
return ret;
}
void debug(int b){
for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
cout<<endl;
}
int update(int i, int y){
if((qNum++)%BUCK==0) rebuild();
move(i, y);
return ans();
}
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'void rebuild()':
elephants.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0; i<bucks.size(); i++) bucks[i].clear();
| ~^~~~~~~~~~~~~
elephants.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
| ~^~~~~~~~~~~~~
elephants.cpp: In function 'int ans()':
elephants.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int b=0; b<bucks.size(); b++){
| ~^~~~~~~~~~~~~
elephants.cpp: In function 'void debug(int)':
elephants.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
| ~^~~~~~~~~~~~~~~~
# | 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... |