oj.uz

Submission #371294

# Submission time Handle Problem Language Result Execution time Memory
371294 2021-02-26T12:08:21 Z oolimry Dungeon 3 (JOI21_ho_t5) C++17
31 / 100
 516 ms 28384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 10092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 11628 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 27228 KB Output is correct
2 Correct 382 ms 27484 KB Output is correct
3 Correct 358 ms 28384 KB Output is correct
4 Correct 426 ms 27356 KB Output is correct
5 Correct 328 ms 28124 KB Output is correct
6 Correct 403 ms 27228 KB Output is correct
7 Correct 405 ms 26844 KB Output is correct
8 Correct 327 ms 26972 KB Output is correct
9 Correct 308 ms 27740 KB Output is correct
10 Correct 171 ms 26076 KB Output is correct
11 Correct 404 ms 27612 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 10092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -