oj.uz

Submission #533240

# Submission time Handle Problem Language Result Execution time Memory
533240 2022-03-05T07:31:23 Z koioi.org-koosaga Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 4000 ms 11688 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
const int MAXN = 1000050;

struct intv{
	int s, e; lint x;
};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<lint> a(n + 1), b(n);
	for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
	for(int i = 0; i < n; i++) cin >> b[i];
	vector<intv> v;
	{
		vector<int> stk;
		vector<int> l(n), r(n);
		for(int i = 0; i < n; i++){
			while(sz(stk) && b[stk.back()] > b[i]){
				stk.pop_back();
			}
			l[i] = (sz(stk) ? stk.back() : -1);
			stk.push_back(i);
		}
		stk.clear();
		for(int i = n-1; i >= 0; i--){
			while(sz(stk) && b[stk.back()] >= b[i]){
				stk.pop_back();
			}
			r[i] = (sz(stk) ? stk.back() : n);
			stk.push_back(i);
		}
		stk.clear();
		for(int i = 0; i < n; i++){
			lint lo = 0;
			if(l[i] >= 0) lo = max(lo, b[l[i]]);
			if(r[i] < n) lo = max(lo, b[r[i]]);
			v.push_back({l[i] + 2, r[i], b[i] - lo});
		}
	}
	for(int i = 0; i < m; i++){
		int s, e; lint x;
		cin >> s >> e >> x;
		e--;
		bool ok = 1;
		for(int j = s; j <= e; j++){
			if(a[j] - a[j-1] > x) ok = 0;
		}
		if(!ok){
			cout << "-1\n";
			continue;
		}
		lint ret = 0;
		for(auto &j : v){
			int ns = max(s, j.s);
			int ne = min(e, j.e);
			if(ne < ns) continue;
			if(ns > s){
				ret += j.x * max(0ll, a[ne] - a[ns - 2] - x);
			}
			else{
				ret += j.x * (a[ne] - a[ns - 1]);
			}
		}
		cout << ret << "\n";
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 588 KB Output is correct
2 Correct 19 ms 580 KB Output is correct
3 Correct 18 ms 620 KB Output is correct
4 Correct 18 ms 620 KB Output is correct
5 Correct 23 ms 588 KB Output is correct
6 Correct 19 ms 608 KB Output is correct
7 Correct 18 ms 588 KB Output is correct
8 Correct 19 ms 576 KB Output is correct
9 Correct 19 ms 624 KB Output is correct
10 Correct 17 ms 608 KB Output is correct
11 Correct 19 ms 644 KB Output is correct
12 Correct 19 ms 588 KB Output is correct
13 Correct 17 ms 588 KB Output is correct
14 Correct 19 ms 616 KB Output is correct
15 Correct 20 ms 620 KB Output is correct
16 Correct 20 ms 588 KB Output is correct
17 Correct 14 ms 576 KB Output is correct
18 Correct 17 ms 568 KB Output is correct
19 Correct 15 ms 600 KB Output is correct
20 Correct 34 ms 608 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4027 ms 4188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 11688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 588 KB Output is correct
2 Correct 19 ms 580 KB Output is correct
3 Correct 18 ms 620 KB Output is correct
4 Correct 18 ms 620 KB Output is correct
5 Correct 23 ms 588 KB Output is correct
6 Correct 19 ms 608 KB Output is correct
7 Correct 18 ms 588 KB Output is correct
8 Correct 19 ms 576 KB Output is correct
9 Correct 19 ms 624 KB Output is correct
10 Correct 17 ms 608 KB Output is correct
11 Correct 19 ms 644 KB Output is correct
12 Correct 19 ms 588 KB Output is correct
13 Correct 17 ms 588 KB Output is correct
14 Correct 19 ms 616 KB Output is correct
15 Correct 20 ms 620 KB Output is correct
16 Correct 20 ms 588 KB Output is correct
17 Correct 14 ms 576 KB Output is correct
18 Correct 17 ms 568 KB Output is correct
19 Correct 15 ms 600 KB Output is correct
20 Correct 34 ms 608 KB Output is correct
21 Execution timed out 4027 ms 4188 KB Time limit exceeded
22 Halted 0 ms 0 KB -