Submission #371314

#	Time	Username	Problem	Language	Result	Execution time	Memory
371314		oolimry	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	754 ms	46192 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
typedef long long lint;
typedef pair<lint, lint> ii;
const lint inf = 1e16;
const int N = 200015;

int n, Q;
lint X[N];
lint B[N];
lint R[N];

lint ans[N];
struct query{ lint U, id, mul; };
vector<query> queries[N];

vector<lint> dis;
int get(lint i){ return upper_bound(all(dis), i) - dis.begin(); }

struct seg{
	lint tree[2*N];
	lint query(int i){
		lint res = 0;
		for(i += N;i > 0;i >>= 1) res += tree[i];
		return res;
	}
	void update(int l, int r, lint x){
		for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
			if(l&1) tree[l++] += x;
			if(r&1) tree[--r] += x;
		}
	}
} m, c;
struct segmax{
	lint tree[2*N];
	lint query(int l, int r){
		lint res = -inf;
		for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
			if(l&1) res = max(res, tree[l++]);
			if(r&1) res = max(res, tree[--r]);
		}
		return res;
	}
	void update(int i, lint x){
		for(i += N;i > 0;i >>= 1) tree[i] = max(tree[i], x);
	}
} finddie;
struct segmin{
	ii tree[2*N];
	ii query(int l, int r){
		ii res = ii(inf,inf);
		for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
			if(l&1) res = min(res, tree[l++]);
			if(r&1) res = min(res, tree[--r]);
		}
		return res;
	}
	void update(int i, ii x){
		for(i += N;i > 0;i >>= 1) tree[i] = min(tree[i], x);
	}
} getmin;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> Q;
	for(int i = 2;i <= n+1;i++) cin >> X[i];
	for(int i = 1;i <= n;i++) cin >> B[i];
	
	fill(m.tree,m.tree + N*2,0); fill(c.tree,c.tree + N*2,0);
	fill(getmin.tree,getmin.tree + 2*N, ii(inf,inf));

	
	for(int i = 2;i <= n+1;i++) finddie.update(i-1, X[i]);
	for(int i = 1;i <= n;i++) getmin.update(i, ii(B[i],i));
	
	for(int i = 2;i <= n+1;i++) X[i] += X[i-1];
		
	for(int q = 1;q <= Q;q++){
		int s, t, u; cin >> s >> t >> u;
		
		if(finddie.query(s,t-1) > u) ans[q] = -1;
		else{
			queries[s].push_back({u,q,1});
			
			int findpos = lower_bound(X+1, X+n+1, X[t] - u) - X;
			lint tmiddle = getmin.query(max(s,findpos),t-1).second;
							
			queries[tmiddle].push_back({u,q,-1});
			ans[q] += (X[t]-X[tmiddle]) * B[tmiddle];
			
			dis.push_back(u);
		}
	}
	
	
	dis.push_back(inf);
	sort(all(dis));
	dis.erase(unique(all(dis)), dis.end());
	
		
	stack<int> st; 
	B[n+1] = -inf; st.push(n+1);
	
	lint maxdis = 0;
	for(int s = n;s >= 1;s--){
		maxdis = max(maxdis, X[s+1]-X[s]);
		while(B[st.top()] >= B[s]){
			///do something about st.top()
			
			int i = st.top();
			lint d1 = get(X[i] - X[s]);
			lint d2 = get(X[R[i]] - X[s]);
			m.update(d1+1, d2, -B[i]);
			c.update(d1+1,d2, (X[i]-X[s]) * B[i]);
			c.update(d2+1,N-1, (X[R[i]]-X[i]) * -B[i]);
			
			st.pop();
		}
		///add the min(Xi+U, Ri)
		int r = st.top();
		R[s] = r;
	
		lint D = get(X[r] - X[s]);
		m.update(1, D, B[s]);
		c.update(D+1, N-1, (X[r]-X[s]) * B[s]);

		st.push(s);
		
		for(query &q : queries[s]){
			ans[q.id] += q.mul * (m.query(get(q.U)) * q.U + c.query(get(q.U)));
		}
	}
	
	for(int q = 1;q <= Q;q++) cout << ans[q] << "\n";
}

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