Submission #1136862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136862		pan	Dungeon 3 (JOI21_ho_t5)	C++20	0 / 100	2410 ms	101248 KiB

Main

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const INF = 1e16;

ll n, q;
ll c[200005], b[200005], ans[200005], nxt[200005];
vector<pii> que[200005];
vector<ll> dis;

ll find_idx(ll x) {return ub(all(dis), x)-dis.begin();}

struct BIT
{
	ll siz;
	vector<ll> fenwick;
	BIT(ll _size = 200100){siz = _size; fenwick.assign(_size, 0);}
	ll ps(ll i)
	{
		ll sum=0;
		while (i>0)
		{
			sum+=fenwick[i];
			i-=i&(-i);
		}
		return sum;
	}
	void update(ll i, ll v)
	{
		while (i<siz)
		{
			fenwick[i]+=v;
			i+=i&(-i);
		}
	}
	void range_update(ll x, ll y, ll v)
	{
		update(x, v);
		update(y + 1, -v);
	}
	
}g, t;

struct node {
    int s, e, m; 
    ll minn, maxx;
    node * l, * r; 
    node(int S, int E) { 
        s = S, e = E, m = (s + e) / 2;
        minn = INF, maxx = -INF;
        if (s != e) { 
            l = new node(s, m); 
            r = new node(m + 1, e); 
        }
    }
    void update(int X, ll V) { 
        if (s == e) minn = min(minn, V), maxx = max(maxx, V);
        else { 
            if (X <= m) l -> update(X, V); 
            else r -> update(X, V); 
            minn = min(l -> minn, r -> minn); 
            maxx = max(l->maxx, r->maxx);
        }
    }
    pi query_min(int S, int E) {
        if (s == S && e == E) return mp(minn, s);
        else if (E <= m) return l -> query_min(S, E);
        else if (S >= m + 1) return r -> query_min(S, E);
        else return min(l -> query_min(S, m), r -> query_min(m + 1, E));
    }
    pi query_max(int S, int E) {
        if (s == S && e == E) return mp(maxx, s);
        else if (E <= m) return l -> query_max(S, E);
        else if (S >= m + 1) return r -> query_max(S, E);
        else return max(l -> query_max(S, m), r -> query_max(m + 1, E));
    }

}* minn, *maxx;


int main()
{
	cin >> n >> q;
	for (ll i=2; i<=n+1; ++i) cin >> c[i];
	for (ll i=1; i<=n; ++i) cin >> b[i];
	minn = new node(1, n + 5); maxx = new node(1, n + 5);
	g = BIT(), t = BIT();
	for (ll i=1; i<=n; ++i) minn->update(i, b[i]);
	for (ll i=2; i<=n+1; ++i) maxx->update(i-1, c[i]);
	for (ll i=2; i<=n + 1; ++i) c[i] += c[i-1];
	for (ll i=0; i<q; ++i)
	{
		ll u, v, m;
		cin >> u >> v >> m;
		if (maxx->query_max(u, v-1).f > m) ans[i] = -1;
		else
		{
			que[u].pb(mp(mp(m, 1), i));
			ll seg = lb(c+1, c + n + 1, c[v] - m)-c;
			show(seg);
			show2(minn->query_min(max(u, seg), v-1).f, minn->query_min(max(u, seg), v-1).s);
			ll pos = minn->query_min(max(u, seg), v-1).s; // min position that will propagate to outside
			show(pos);
			que[pos].pb(mp(mp(m, -1), i));
			ans[i] += (c[v] - c[pos])*b[pos];
			dis.pb(m);
		}
	}
	dis.pb(INF);
	discretize(dis); 
	deque<ll> dq;
	b[n+1] = -INF;
	dq.pb(n + 1);
	for (ll i=n; i>0; --i)
	{
		while ( b[dq.back()] >= b[i]) 
		{
			ll now = dq.back();
			ll x =find_idx(c[now] - c[i]), y = find_idx(c[nxt[now]] - c[i]);
			g.range_update(x + 1, y, -b[now]);
			t.range_update(x + 1, y, (c[now] - c[i])*b[now]);
			t.range_update(y + 1, dis.size(), -(c[nxt[now]] - c[now])*b[now]);
			dq.pop_back();
		}
		nxt[i] = dq.back();
		ll x = find_idx(c[nxt[i]] - c[i]);
		g.range_update(1, x, b[i]);
		t.range_update(x +1, dis.size(), (c[nxt[i]] - c[i])*b[i]);
		dq.pb(i);
		for (pii u: que[i]) 
		{
			ll x = find_idx(u.f.f);
			ans[u.s] += u.f.s * ((g.ps(x)) * u.f.f  + t.ps(x));
		}
	}
	for (ll i=0; i<q; ++i) cout << ans[i] << endl;
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44