This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const int mxN = 1e6;
ll n,a[mxN],idx1[mxN],q,st,mx,last[mxN];
struct segtree{
vector<pair<ll,illnt>> v;
ll sz = 1;
void init(){
while(sz < n) sz *= 2;
v.assign(2 * sz, {0LL, 0LL});
}
void set(ll val, ll i, ll x, ll l, ll r){
if(r - l == 1){
v[x] = {val, i};
return;
}
ll mid = l + (r - l) / 2;
if(i < mid) set(val, i, 2 * x + 1, l, mid);
else set(val, i, 2 * x + 2, mid, r);
v[x] = max(v[2 * x + 1], v[2 * x + 2]);
}
void set(ll val, ll i){
set(val, i, 0, 0, sz);
}
pair<ll,ll> find(ll l, ll r, ll x, ll lx, ll rx){
if(lx >= r or rx <= l) return {0, 0};
if(lx >= l and rx <= r) return v[x];
ll mid = lx + (rx - lx) / 2;
return max(find(l, r, 2 * x + 1, lx, mid), find(l, r, 2 * x + 2, mid, rx));
}
pair<ll,ll> find(ll l, ll r){
return find(l, r, 0, 0, sz);
}
pair<ll,ll> find1(ll val, ll l, ll r, ll op, ll x, ll lx, ll rx){
if(lx >= r or rx <= l) return {-1, -1};
if(rx - lx == 1){
if(v[x].first > val) return v[x];
return {-1, -1};
}
ll mid = lx + (rx - lx) / 2;
pair<ll,ll> ans = find1(val, l, r, op, 2 * x + 1 + op, ((!op) ? (lx) : (mid)), ((!op) ? (mid) : (rx)));
if(ans.first > val) return ans;
ans = find1(val, l, r, op, 2 * x + 2 - op, ((!op) ? (mid) : (lx)), ((!op) ? (rx) : (mid)));
if(ans.first > val) return ans;
return {-1, -1};
}
pair<ll,ll> find1(ll val, ll l, ll r, ll op){
return find1(val, l, r, op, 0, 0, sz);
}
};
segtree s;
void f(ll idx, ll val){
if(val == mx){
a[idx] = ++last[mx];
idx1[mx] = idx;
s.set(a[idx], idx);
return;
}
a[idx] = last[val];
ll idx2 = idx1[val];
idx1[val] = idx;
s.set(a[idx], idx);
f(idx2, val + 1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> st;
mx = min(10LL, n);
st--;
s.init();
for(int i = 0; i < n; i++){
cin >> a[i];
if(n - a[i] <= mx - 2){
s.set(a[i] + mxN, i);
last[n - a[i] + 1] = a[i] + mxN;
idx1[n - a[i] + 1] = i;
a[i] += mxN;
}
else s.set(a[i], i);
if(n - a[i] == mx - 1){
idx1[n - a[i] + 1] = i;
last[mx] = a[i];
}
}
//5 3
//5 1 2 4 3
//1
//F 2
cin >> q;
while(q--){
char op;
cin >> op;
if(op == 'F'){
ll idx;
cin >> idx;
idx--;
if(idx == st){
cout << 0 << '\n';
continue;
}
pair<ll,ll> x,x1;
if(idx < st){
x = s.find(idx, st);
x1 = s.find1(x.first, st + 1, n, 0);
if(x1.first <= x.first) cout << n - 1 - idx << '\n';
else cout << x1.second - idx - 1 << '\n';
}
else{
x = s.find(st + 1, idx + 1);
x1 = s.find1(x.first, 0, st, 1);
if(x1.first <= x.first) cout << idx << '\n';
else cout << idx - x1.second - 1 << '\n';
}
}
else{
ll idx,val;
cin >> idx >> val;
idx--;
f(idx, val);
// cout << "--> ";
// for(int i = 0; i < n; i++) cout << a[i] << ' ';
// cout << '\n';
}
}
}
//5 3
//5 1 2 4 3
//2
//E 2 1
//F 2
Compilation message (stderr)
cake.cpp:10:17: error: 'illnt' was not declared in this scope; did you mean 'int'?
10 | vector<pair<ll,illnt>> v;
| ^~~~~
| int
cake.cpp:10:17: error: template argument 2 is invalid
cake.cpp:10:22: error: template argument 1 is invalid
10 | vector<pair<ll,illnt>> v;
| ^~
cake.cpp:10:22: error: template argument 2 is invalid
cake.cpp: In member function 'void segtree::init()':
cake.cpp:15:5: error: request for member 'assign' in '((segtree*)this)->segtree::v', which is of non-class type 'int'
15 | v.assign(2 * sz, {0LL, 0LL});
| ^~~~~~
cake.cpp: In member function 'void segtree::set(int, int, int, int, int)':
cake.cpp:20:5: error: invalid types 'int[int]' for array subscript
20 | v[x] = {val, i};
| ^
cake.cpp:26:4: error: invalid types 'int[int]' for array subscript
26 | v[x] = max(v[2 * x + 1], v[2 * x + 2]);
| ^
cake.cpp:26:15: error: invalid types 'int[int]' for array subscript
26 | v[x] = max(v[2 * x + 1], v[2 * x + 2]);
| ^
cake.cpp:26:29: error: invalid types 'int[int]' for array subscript
26 | v[x] = max(v[2 * x + 1], v[2 * x + 2]);
| ^
cake.cpp: In member function 'std::pair<int, int> segtree::find(int, int, int, int, int)':
cake.cpp:35:35: error: invalid types 'int[int]' for array subscript
35 | if(lx >= l and rx <= r) return v[x];
| ^
cake.cpp: In member function 'std::pair<int, int> segtree::find1(int, int, int, int, int, int, int)':
cake.cpp:47:8: error: invalid types 'int[int]' for array subscript
47 | if(v[x].first > val) return v[x];
| ^
cake.cpp:47:33: error: invalid types 'int[int]' for array subscript
47 | if(v[x].first > val) return v[x];
| ^
cake.cpp: In function 'int main()':
cake.cpp:83:18: error: no matching function for call to 'min(long long int, int&)'
83 | mx = min(10LL, n);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from cake.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
cake.cpp:83:18: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
83 | mx = min(10LL, n);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from cake.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
cake.cpp:83:18: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
83 | mx = min(10LL, n);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cake.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
cake.cpp:83:18: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
83 | mx = min(10LL, n);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cake.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
cake.cpp:83:18: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
83 | mx = min(10LL, n);
| ^