Submission #817824

#	Time	Username	Problem	Language	Result	Execution time	Memory
817824		denniskim	Dungeon 3 (JOI21_ho_t5)	C++17	0 / 100	379 ms	53904 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll S, T, U;
	ll num;
	
	bool operator < (const gujo &xx) const
	{
		return S > xx.S;
	}
};

ll n, m;
ll a[200010], b[200010];
gujo Q[200010];
ll X[200010];
ll L[200010], R[200010];
vector<ll> yL[200010];
vector<ll> zip;
ll siz;
ll ans[200010];

void getL(void)
{
	stack<pll> stk;
	stack<ll> nstk;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		while(!stk.empty() && stk.top().fi >= b[i])
		{
			stk.pop();
			nstk.pop();
		}
		
		if(stk.empty())
			L[i] = -INF;
		
		else
		{
			L[i] = stk.top().se;
			yL[nstk.top()].push_back(i);
		}
		
		stk.push({b[i], X[i]});
		nstk.push(i);
	}
}

void getR(void)
{
	stack<pll> stk;
	
	for(ll i = n ; i >= 1 ; i--)
	{
		while(!stk.empty() && stk.top().fi > b[i])
			stk.pop();
		
		if(stk.empty())
			R[i] = X[n + 1];
		else
			R[i] = stk.top().se;
		
		stk.push({b[i], X[i]});
	}
}

struct segtree
{
	ll seg[1000010];
	
	void update(ll no, ll s, ll e, ll w, ll v)
	{
		if(e < w || w < s)
			return;
		
		if(s == e)
		{
			seg[no] = v;
			return;
		}
		
		update(no << 1, s, (s + e) >> 1, w, v);
		update(no << 1 | 1, ((s + e) >> 1) + 1, e, w, v);
		
		seg[no] = max(seg[no << 1], seg[no << 1 | 1]);
	}
	
	ll query(ll no, ll s, ll e, ll l, ll r)
	{
		if(e < l || r < s)
			return MIN;
		
		if(l <= s && e <= r)
			return seg[no];
		
		return max(query(no << 1, s, (s + e) >> 1, l, r), query(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r));
	}
}segt;

struct fenwicktree
{
	ll bit[5000010];
	
	void update(ll w, ll v)
	{
		for(ll i = w ; i <= siz ; i += (i & (-i)))
			bit[i] += v;
	}
	
	ll query(ll w)
	{
		ll ret = 0;
		
		for(ll i = w ; i > 0 ; i -= (i & (-i)))
			ret += bit[i];
		
		return ret;
	}
}ABIT, BBIT;

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	for(ll i = 1 ; i <= n ; i++)
		cin >> a[i];
	
	for(ll i = 1 ; i <= n ; i++)
		cin >> b[i];
	
	for(ll i = 1 ; i <= m ; i++)
	{
		cin >> Q[i].S >> Q[i].T >> Q[i].U;
		Q[i].num = i;
	}
	
	sort(Q + 1, Q + 1 + m);
	
	X[1] = 0;
	
	for(ll i = 2 ; i <= n + 1 ; i++)
		X[i] = X[i - 1] + a[i - 1];
	
	getL();
	getR();
	
	zip.push_back(0);
	zip.push_back(INF);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		if(L[i] != -INF)
		{
			zip.push_back(X[i] - L[i]);
			zip.push_back(R[i] - L[i]);
		}
		
		zip.push_back(R[i] - X[i]);
	}
	
	compress(zip);
	siz = (ll)zip.size();
	
	for(ll i = 1 ; i <= n ; i++)
		segt.update(1, 1, n, i, a[i]);
	
	ll p = n;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		if(segt.query(1, 1, n, Q[i].S, Q[i].T - 1) > Q[i].U)
		{
			ans[Q[i].num] = -1;
			continue;
		}
		
		while(p >= Q[i].S)
		{
			ll w = R[p] - X[p];
			ll idx = lower_bound(zip.begin(), zip.end(), w) - zip.begin() + 1;
			
			if(p)
			{
				ABIT.update(1, b[p]);
				ABIT.update(idx, -b[p]);
				BBIT.update(idx, b[p] * w);
			}
			
			for(auto &j : yL[p])
			{
				w = X[j] - L[j];
				idx = lower_bound(zip.begin(), zip.end(), w) - zip.begin() + 1;
				ll w2 = R[j] - L[j];
				ll idx2 = lower_bound(zip.begin(), zip.end(), w2) - zip.begin() + 1;
				ll w3 = R[j] - X[j];
				ll idx3 = lower_bound(zip.begin(), zip.end(), w3) - zip.begin() + 1;
				
				ABIT.update(1, -b[j]);
				ABIT.update(idx3, b[j]);
				BBIT.update(idx3, -b[j] * w3);
				
				if(w < w3)
				{
					ABIT.update(1, b[j]);
					ABIT.update(idx, -b[j]);
					BBIT.update(idx, b[j] * w);
					BBIT.update(idx3, -b[j] * w);
					ABIT.update(idx3, -b[j]);
					BBIT.update(idx3, b[j] * w2);
					ABIT.update(idx2, b[j]);
					BBIT.update(idx2, -b[j] * w2);
				}
				
				else
				{
					ABIT.update(1, b[j]);
					ABIT.update(idx3, -b[j]);
					BBIT.update(idx3, b[j] * w3);
					BBIT.update(idx, -b[j] * w3);
					ABIT.update(idx, -b[j]);
					BBIT.update(idx, b[j] * w2);
					ABIT.update(idx2, b[j]);
					BBIT.update(idx2, -b[j] * w2);
				}
			}
			
			p--;
		}
		
		ll idx = lower_bound(zip.begin(), zip.end(), Q[i].U) - zip.begin();
		ll A = ABIT.query(idx);
		ll B = BBIT.query(idx);
		
		ans[Q[i].num] = A * Q[i].U + B;
	}
	
	ll cc = 1;
	
	for(ll i = 1 ; i <= m ; i++)
		cout << ans[i] en;
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:257:5: warning: unused variable 'cc' [-Wunused-variable]
  257 |  ll cc = 1;
      |     ^~

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