#include <bits/stdc++.h>
#include "elephants.h"
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int uwu = 400;
int L, n;
struct block {
vector <pii> v;
int cnt[2 * uwu + 1], pos[2 * uwu + 1];
void build (){
if (v.empty()) return;
int r = v.size();
r--;
cnt[r] = 1, pos[r] = v[r].st;
ford (l, r, 0){
while (v[r].st - v[l].st > L)
r--;
if (r == v.size() - 1)
cnt[l] = 1, pos[l] = v[l].st;
else cnt[l] = cnt[r + 1] + 1, pos[r + 1];
}
}
void ins (int val, int id){
v.pb({val, id});
int i = v.size();
i--;
while (i > 0 && v[i] < v[i - 1])
swap(v[i], v[i - 1]), i--;
}
void ers (int id){
int j;
forf (i, 0, v.size())
if (v[i].nd == id)
j = i;
forf (i, j, v.size() - 1)
swap(v[j], v[j + 1]);
v.pop_back();
}
pii get (int u){
if (u + L >= v.back().st)
return {u, 0};
// cout << "get " << v.back().st << " " << v.back().nd << "\n";
int k = upper_bound(all(v), mp(u + L - 1, 0)) - v.begin();
return {pos[k], cnt[k]};
}
void debug (){
forf (i, 0, v.size())
cout <<v[i].st << " " << v[i].nd << " " << cnt[i] << " " << pos[i] << "\n";
}
};
block b[uwu + 5];
pii a[N];
int pos[N], cnt;
void rs (){
int j = 0;
forr (i, 0, uwu)
for (pii w : b[i].v)
a[++j] = w;
forr (i, 0, uwu)
b[i].v.clear();
forr (i, 1, n)
b[i / uwu].ins(a[i].st, a[i].nd), pos[a[i].nd] = i / uwu;
forr (i, 0, uwu)
b[i].build();
}
void debug(){
forr (i, 0, uwu)
cout << i << ":\n",b[i].debug();
}
void init (int _n, int _l, int _x[]){
n = _n;
L = _l;
forr (i, 1, n)
a[i].st = _x[i], a[i].nd = i;
sort(a + 1, a + 1 + n);
rs();
}
int update (int u, int w){
//cout << L << "\n";
if (cnt > uwu)
rs();
cnt++;
//return 0;
int j = uwu;
forr (i, 1, uwu){
if (b[i].v.empty()) {
j = i - 1;
break;
}
if (b[i].v[0].st > w){
j = i - 1;
break;
}
}
u++;
b[pos[u]].ers(u);
b[pos[u]].build();
b[j].ins(w, u);
b[j].build();
pos[u] = j;
//debug();
int d = 0, ans = 0;
forr (i, 0, uwu)
if (!b[i].v.empty()){
d = b[i].v[0].st;
break;
}
forr (i, 0, uwu){
//cout << d << " " << ans << "\n";
if (b[i].v.empty()) continue;
pii tmp = b[i].get(d);
d = tmp.st;
ans += tmp.nd;
}
return ans + 1;
}
Compilation message
elephants.cpp: In member function 'void block::build()':
elephants.cpp:40:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (r == v.size() - 1)
| ~~^~~~~~~~~~~~~~~
elephants.cpp:42:43: warning: right operand of comma operator has no effect [-Wunused-value]
42 | else cnt[l] = cnt[r + 1] + 1, pos[r + 1];
| ~~~~~~~~~^
elephants.cpp: In member function 'void block::ers(int)':
elephants.cpp:5:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
| ^
elephants.cpp:57:3: note: in expansion of macro 'forf'
57 | forf (i, 0, v.size())
| ^~~~
elephants.cpp:5:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
| ^
elephants.cpp:60:3: note: in expansion of macro 'forf'
60 | forf (i, j, v.size() - 1)
| ^~~~
elephants.cpp: In member function 'void block::debug()':
elephants.cpp:5:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
| ^
elephants.cpp:74:3: note: in expansion of macro 'forf'
74 | forf (i, 0, v.size())
| ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:60:9: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
60 | forf (i, j, v.size() - 1)
| ^
elephants.cpp:56:7: note: 'j' was declared here
56 | int j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
