Submission #371294

#	Time	Username	Problem	Language	Result	Execution time	Memory
371294		oolimry	Dungeon 3 (JOI21_ho_t5)	C++17	31 / 100	516 ms	28384 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;

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

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

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

struct seg{
	lint tree[400015];
	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;

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];
	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;
		assert(t == n+1);
		queries[s].push_back({u,q});
		dis.push_back(u);
	}
	
	dis.push_back(inf);
	sort(all(dis));
	dis.erase(unique(all(dis)), dis.end());
	N = sz(dis)+2;
	
	fill(m.tree,m.tree+400014,0); fill(c.tree,c.tree+400014,0);
	
	stack<int> st; 
	B[n+1] = -inf; st.push(n+1);
	
	lint maxdis = 0;
	for(int s = n;s >= 1;s--){
		//show(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]);
			//cout << "m: " << d1+1 << " " << d2 << " " << -B[i] << endl;
			
			c.update(d1+1,d2, (X[i]-X[s]) * B[i]);
			//cout << "c: " << d1+1 << " " << d2 << " " << (X[i]-X[s]) * B[i] << endl;

			c.update(d2+1,N-1, (X[R[i]]-X[i]) * -B[i]);
			//cout << "c: " << d2+1 << " " << N-1 << " " << (X[R[i]]-X[i]) * -B[i] << endl;
			
			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]);
		//cout << "m: " << 1 << " " << D << " " << B[s] << endl;

		c.update(D+1, N-1, (X[r]-X[s]) * B[s]);
		//cout << "c: " << D+1 << " " << N-1 << " " << (X[r]-X[s]) * B[s] << endl;

		st.push(s);
		
		for(query &q : queries[s]){
			if(q.U < maxdis) ans[q.id] = -1;
			else ans[q.id] = 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: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 31 / 31
• Subtask 4: 0 / 44