#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pair<int, int>>;
using pl = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pl>;
using ld = long double;
#define all(v) (v).begin(), (v).end()
#define ar array
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
os << '{';
string sep;
for (const T &x : v)
os << sep << x, sep = ", ";
return os << '}';
}
void dbg_out()
{
cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
cerr << ' ' << H;
dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const int N = 1<<20;
int a[N], res=0, previous=0;
int mi[N], mx[N];
int leftmost[N], n, m, k;
vector<pair<int,pi>> mem;
void addleft(int idx){
mem.pb({0, {a[idx], mi[a[idx]]}});
mem.pb({1, {a[idx], mx[a[idx]]}});
mi[a[idx]] = idx;
if (mx[a[idx]]<0) mx[a[idx]] = idx;
res = max(res, mx[a[idx]]-mi[a[idx]]);
}
void addright(int idx){
mx[a[idx]] = idx;
if (mi[a[idx]]>n) mx[a[idx]] = idx;
res = max(res, mx[a[idx]]-mi[a[idx]]);
}
void snapshot(){
previous = res;
}
void rollback(){
while(sz(mem)){
pair<int,pi> p = mem.back();
if (p.fi==0){
mi[p.se.fi] = p.se.se;
}else{
mx[p.se.fi] = p.se.se;
}
mem.pop_back();
}
res = previous;
}
void init(){
for (int i=1;i<=m;++i) mi[i] = INF, mx[i] = -INF;
res = 0;
}
const int block=320; //Dont forget to set
struct Query {
int l, r, idx;
inline pair<int, int> toPair() const {
return make_pair(l / block, r);
}
};
inline bool operator<(const Query &a, const Query &b) {
return a.toPair() < b.toPair();
}
using vq = vector<Query>;
vi mo(vq queries) {
vi answers(queries.size());
sort(queries.begin(), queries.end());
/*
Light Queries
*/
for (Query q: queries){
if (q.r-q.l+1<=block){
int ans = 0;
for (int j=q.l;j<=q.r;++j){
leftmost[a[j]] = INF;
}
for (int j=q.l;j<=q.r;++j){
ans = max(ans, j-leftmost[a[j]]);
if(leftmost[a[j]]>=n) leftmost[a[j]] = j;
}
answers[q.idx] = ans;
}
}
/*
Heavy Queries
*/
int l, r;
int last_bucket = -1;
for (Query q : queries) {
if (q.r-q.l+1<=block) continue;
int bucket = q.l/block;
if (bucket!=last_bucket){
init();
l = (bucket+1)*block;
if (l>=n) l = n;
r = q.r;
for (int j=l;j<=r;++j){
addright(j);
}
}
last_bucket = bucket;
while(r<q.r){
addright(++r);
}
snapshot();
for (int j=l-1;j>=q.l;--j){
addleft(j);
}
answers[q.idx] = res;
rollback();
}
return answers;
}
void solve()
{
cin >> n >> m>>k;
for (int i=0;i<n;++i) cin >> a[i];
vq q(k);
for (int i=0;i<k;++i){
int l,r;
cin >> l >> r;
l--;r--;
q[i] = {l,r,i};
}
vi ans = mo(q);
for (int x:ans) cout << x <<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
}
I think a struct like the one below is really convenient for these types of problems.
The usage is basically:
save
on every variable of relevance before you change it (only once after every checkpoint is really necessary).rollback
to revert to the previous state (to the way things were when you last made a checkpoint).Wow, that is pretty nice. I think I did something similar to what the struct does, but my implementation is nowhere near as structured as that. I will try to implement the structure and hope my issue resolves.
Auto comment: topic has been updated by Bungmint (previous revision, new revision, compare).