Submission #485535

#	Time	Username	Problem	Language	Result	Execution time	Memory
485535		Killer2501	Triple Jump (JOI19_jumps)	C++14	100 / 100	935 ms	110528 KiB

jumps

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "hopscotch"
#define ppl pair<ll, pll>
using namespace std;
using ll = long long;
const int  N = 5e5+55;
const ll mod = 1e15;
const ll base = 350;
const ll inf = 1e12;
ll m, n, t, k, a[N], ans, tong, b[N], c[N], d[N], l[N], r[N], res[N];
vector<pll> adj[N];
vector<ll> kq;
struct BIT
{
    vector<ll> fe;
    ll n;
    BIT(ll _n)
    {
        n = _n;
        fe.resize(n+1, 0);
    }
    void clear()
    {
    	fill(fe.begin(), fe.end(), 0);
    }
    void add(ll id, ll x)
    {
        for(; id <= n; id += id & -id)fe[id] += x;
    }
    void add(ll l, ll r, ll x)
    {
        if(l > r)return;
        add(l, x);
        add(r+1, -x);
    }
    ll get(ll id)
    {
        ll total = 0;
        for(; id; id -= id & -id)total += fe[id];
        return total;
    }
};
struct IT
{
	vector<ll> st, lazy, vi;
	IT(ll _N)
	{
		n = _N;
		st.resize(n*4+4, 0);
		lazy.resize(n*4+4, 0);
		vi.resize(n*4+4, 0);
	}
	void build(ll id, ll l, ll r)
	{
		if(l == r)
		{
			vi[id] = a[l];
			return;
		}
		ll mid = (l+r)/2;
		build(id*2, l, mid);
		build(id*2+1, mid+1, r);
		st[id] = vi[id] = max(vi[id*2], vi[id*2+1]);
	}
	void build()
	{
		build(1, 1, n);
	}
	void down(ll id)
	{
		if(!lazy[id])return;
		st[id*2] = max(st[id*2], vi[id*2] + lazy[id]);
		st[id*2+1] = max(st[id*2+1], vi[id*2+1] + lazy[id]);
		lazy[id*2] = max(lazy[id*2], lazy[id]);
		lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
		lazy[id] = 0;
	}
	void update(ll id, ll l, ll r, ll u, ll v, ll x)
	{
		if(u <= l && r <= v)
		{
			st[id] = max(st[id], x+vi[id]);
			lazy[id] = max(lazy[id], x);
			return;
		}
		if(u > r || l > v)return;
		down(id);
		ll mid = (l+r)/2;
		update(id*2, l, mid, u, v, x);
		update(id*2+1, mid+1, r, u, v, x);
		st[id] = max(st[id*2], st[id*2+1]);
	}
	void update(ll l, ll r, ll x)
	{
		if(l > r)return;
		update(1, 1, n, l, r, x);
	}
	ll get(ll id, ll l, ll r, ll u, ll v)
	{
		if(u <= l && r <= v)return st[id];
		if( u > r || l > v)return -inf;
		down(id);
		ll mid = (l+r)/2;
		return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
	}
	ll get(ll l, ll r)
	{
		return get(1, 1, n, l, r);
	}
};
vector<pll> v;
struct query
{
	ll l, r, id;
	bool operator < (const query& q)
	{
		return (l > q.l);
	}
}q[N];
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		while(!kq.empty() && a[kq.back()] < a[i])kq.pop_back();
		if(!kq.empty())v.pb({kq.back(), i});
		kq.pb(i);
	}
	kq.clear();
	for(int i = n; i > 0; i --)
	{
		while(!kq.empty() && a[kq.back()] < a[i])kq.pop_back();
		if(!kq.empty())v.pb({i, kq.back()});
		kq.pb(i);
	}
    cin >> m;
    for(int i = 1; i <= m; i ++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q+1, q+1+m);
	sort(v.rbegin(), v.rend());
	IT it(n);
	it.build();
	for(int i = 1, j = 0; i <= m; i ++)
	{
		while(j < v.size() && v[j].fi >= q[i].l)
		{
			it.update(v[j].se*2-v[j].fi, n, a[v[j].se]+a[v[j].fi]);
			++j;
		}
		b[q[i].id] = it.get(q[i].l, q[i].r);
	}
	for(int i = 1; i <= m; i ++)cout << b[i] <<'\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".in", "r"))
    {
        freopen(task".in", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
5 4
1 2 1
2 3 4
1 4 3
4 3 2
3
1 3 1
1 3 2
1 3 3
*/

Compilation message (stderr)

jumps.cpp: In function 'void sol()':
jumps.cpp:153:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   while(j < v.size() && v[j].fi >= q[i].l)
      |         ~~^~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen(task".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54