#include "elephants.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
int n;
int l;
vector <vector <int> > a;
vector <vector <pii> >bl(150001);
vector <int> vec;
int blsize = 500;
vector <int> le,ri;
multiset <int> st;
void process(int ind){
bl[ind].resize(a[ind].size());
int x = bl[ind].size();
bl[ind][x - 1] = {0, x - 1};
int cur = x;
for(int i = x - 2; i >= 0; i--){
while(a[ind][cur - 1] > a[ind][i] + l){
cur--;
}
if(cur == x){
bl[ind][i] = {0, i};
}
else{
bl[ind][i] = {bl[ind][cur].f + 1, bl[ind][cur].s};
}
}
// cout << 1;
}
void er(int x){
st.erase(st.find(x));
for(int i = 0; i < le.size(); i++){
if(le[i] <= x && ri[i] >= x){
for(int j = 0; j < a[i].size(); j++){
if(a[i][j] == x) {
a[i].erase(a[i].begin() + j);
break;
}
}
//for(int to : a[i]) cout << to << ' ';
process(i);
break;
}
}
// cout << 1;
}
void in(int x){
st.insert(x);
for(int i = 0; i < le.size(); i++){
if(le[i] <= x && ri[i] >= x){
a[i].pb(x);
for(int j = a[i].size() - 2; j >= 0; j--){
if(a[i][j] < x) break;
swap(a[i][j], a[i][j + 1]);
}
// for(int to : a[i]) cout << to << ' ';
process(i);
break;
}
}
// cout << 1;
}
int A[150001];
void init(int N, int L, int x[])
{
n = N;
l = L;
for(int i = 0; i < n; i++) A[i] = x[i];
for(int i = 0; i < n; i++) st.insert(x[i]);
}
void init1(){
vector <int> cur;
le.clear();
a.clear();
ri.clear();
for(int to : st){
cur.pb(to);
if(cur.size() == blsize) a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
}
if(!cur.empty()){
a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
}
ri.back() = INT_MAX;
for(int i = 0; i < a.size(); i++) process(i);
}
int getans(){
int ans = 0;
int cur = 0;
int nx = a[0][0];
for(int i = 0; i < a.size(); i++){
if(le[i] > nx || ri[i] < nx) continue;
int L = -1, R = a[i].size();
while(L + 1 < R){
int m = (L + R) / 2;
if(a[i][m] >= nx) R = m;
else L = m;
}
ans += bl[i][R].f + 1;
//cout << l << "\n";
nx = bl[i][R].s + l + 1;
}
//cout << 1;
return ans;
}
int cnt = 0;
int update(int i, int y)
{
er(A[i]);
A[i] = y;
in(A[i]);
if(cnt % blsize == 0) init1();
return getans();
}
Compilation message
elephants.cpp: In function 'void er(int)':
elephants.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < le.size(); i++){
| ~~^~~~~~~~~~~
elephants.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int j = 0; j < a[i].size(); j++){
| ~~^~~~~~~~~~~~~
elephants.cpp: In function 'void in(int)':
elephants.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < le.size(); i++){
| ~~^~~~~~~~~~~
elephants.cpp: In function 'void init1()':
elephants.cpp:93:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
93 | if(cur.size() == blsize) a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
| ~~~~~~~~~~~^~~~~~~~~
elephants.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < a.size(); i++) process(i);
| ~~^~~~~~~~~~
elephants.cpp: In function 'int getans()':
elephants.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
elephants.cpp:105:9: warning: unused variable 'cur' [-Wunused-variable]
105 | int cur = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 7 |
Incorrect |
19 ms |
5204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 7 |
Incorrect |
19 ms |
5204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 7 |
Incorrect |
19 ms |
5204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
