oj.uz

Submission #826761

# Submission time Handle Problem Language Result Execution time Memory
826761 2023-08-16T02:48:12 Z maomao90 Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 4000 ms 4432 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 500005;

int n, q;
int a[MAXN], b[MAXN];

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n >> q;
	REP (i, 1, n + 1) {
		cin >> a[i];
	}
	REP (i, 1, n + 1) {
		cin >> b[i];
	}
	while (q--) {
		int s, t, u; cin >> s >> t >> u;
		ll ans = 0;
		set<ii> st;
		int tot = 0;
		REP (i, s, t) {
			if (a[i] > u) {
				ans = -1;
				break;
			}
			tot += INF;
			st.insert({b[i], INF});
			int need = a[i];
			while (need) {
				auto [cost, cnt] = *st.begin(); st.erase(st.begin());
				int mn = min(need, cnt);
				need -= mn;
				cnt -= mn;
				ans += (ll) cost * mn;
				tot -= mn;
				if (cnt) {
					st.insert({cost, cnt});
				}
			}
			while (tot > u - a[i]) {
				auto [cost, cnt] = *prev(st.end()); st.erase(prev(st.end()));
				int mn = min(tot - (u - a[i]), cnt);
				cnt -= mn;
				tot -= mn;
				if (cnt) {
					st.insert({cost, cnt});
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 464 KB Output is correct
2 Correct 492 ms 588 KB Output is correct
3 Correct 358 ms 460 KB Output is correct
4 Correct 427 ms 568 KB Output is correct
5 Correct 502 ms 604 KB Output is correct
6 Correct 339 ms 468 KB Output is correct
7 Correct 426 ms 436 KB Output is correct
8 Correct 494 ms 716 KB Output is correct
9 Correct 308 ms 444 KB Output is correct
10 Correct 384 ms 572 KB Output is correct
11 Correct 440 ms 500 KB Output is correct
12 Correct 299 ms 600 KB Output is correct
13 Correct 434 ms 476 KB Output is correct
14 Correct 328 ms 576 KB Output is correct
15 Correct 327 ms 452 KB Output is correct
16 Correct 479 ms 612 KB Output is correct
17 Correct 270 ms 560 KB Output is correct
18 Correct 327 ms 480 KB Output is correct
19 Correct 212 ms 456 KB Output is correct
20 Correct 1422 ms 532 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4006 ms 1720 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 4029 ms 4432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 464 KB Output is correct
2 Correct 492 ms 588 KB Output is correct
3 Correct 358 ms 460 KB Output is correct
4 Correct 427 ms 568 KB Output is correct
5 Correct 502 ms 604 KB Output is correct
6 Correct 339 ms 468 KB Output is correct
7 Correct 426 ms 436 KB Output is correct
8 Correct 494 ms 716 KB Output is correct
9 Correct 308 ms 444 KB Output is correct
10 Correct 384 ms 572 KB Output is correct
11 Correct 440 ms 500 KB Output is correct
12 Correct 299 ms 600 KB Output is correct
13 Correct 434 ms 476 KB Output is correct
14 Correct 328 ms 576 KB Output is correct
15 Correct 327 ms 452 KB Output is correct
16 Correct 479 ms 612 KB Output is correct
17 Correct 270 ms 560 KB Output is correct
18 Correct 327 ms 480 KB Output is correct
19 Correct 212 ms 456 KB Output is correct
20 Correct 1422 ms 532 KB Output is correct
21 Execution timed out 4006 ms 1720 KB Time limit exceeded
22 Halted 0 ms 0 KB -