oj.uz

Submission #682701

# Submission time Handle Problem Language Result Execution time Memory
682701 2023-01-16T20:03:31 Z flappybird Fire (JOI20_ho_t5) C++17
1 / 100
 1000 ms 54184 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
typedef pair<pll, pll> T;
pll operator+(pll p1, pll p2) { return pll(p1.first + p2.first, p1.second + p2.second); }
T operator+(T p1, T p2) { return T(p1.first + p2.first, p1.second + p2.second); }
pll operator-(pll p1, pll p2) { return pll(p1.first - p2.first, p1.second - p2.second); }
T operator-(T p1, T p2) { return T(p1.first - p2.first, p1.second - p2.second); }
struct fenwick {
	vector<T> tree;
	int N;
	fenwick(int N = 0) :N(N) {
		tree.resize(N + 1);
	}
	void upd(int i, T x) {
		while (i <= N) {
			tree[i] = tree[i] + x;
			i += i & -i;
		}
	}
	T get(int i) {
		T ans({ 0, 0 }, { 0, 0 });
		while (i) {
			ans = ans + tree[i];
			i -= i & -i;
		}
		return ans;
	}
};
vector<pair<int, pll>> del[MAX];
int arr[MAX];
int l[MAX];
int r[MAX];
int last[MAX];
vector<tuple<int, int, int>> qv[MAX];
T line[MAX];
ll ans[MAX];
fenwick bit;
int N;
inline ll get(int i, int t) {
	if (i < 1) return 0ll;
	int l, r;
	l = 0;
	r = N + 1;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		auto res = bit.get(mid);
		if (t * res.first.first + res.first.second > i) r = mid;
		else l = mid;
	}
	auto res = bit.get(l);
	int ind = t * res.first.first + res.first.second;
	return 1ll * arr[l + 1] * (i - res.first.first * t - res.first.second) + res.second.first * t + res.second.second;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int Q;
	cin >> N >> Q;
	int i;
	for (i = 1; i <= N; i++) cin >> arr[i];
	vector<pii> stk = { { 1e9 + 10, 0 } };
	for (i = 1; i <= N; i++) r[i] = N + 1;
	for (i = 1; i <= N; i++) {
		while (stk.back().first < arr[i]) {
			r[stk.back().second] = i;
			stk.pop_back();
		}
		l[i] = stk.back().second;
		stk.emplace_back(arr[i], i);
	}
	for (i = 1; i <= N; i++) {
		del[0].emplace_back(i, pll(1, arr[i]));
		if (l[i]) {
			del[i - l[i]].emplace_back(i, pll(-1, -arr[i]));
			del[r[i] - l[i]].emplace_back(i, pll(1, arr[i]));
		}
		del[r[i] - i].emplace_back(i, pll(-1, -arr[i]));
	}
	int low, high, t;
	for (i = 1; i <= Q; i++) {
		cin >> t >> low >> high;
		qv[t].emplace_back(low, high, i);
	}
	bit = fenwick(N);
	for (i = 0; i <= N; i++) {
		for (auto& [loc, p] : del[i]) {
			T pv = line[loc];
			auto& [a, b] = line[loc].first;
			auto& [c, d] = line[loc].second;
			a = line[loc].first.first;
			b = line[loc].first.second;
			ll y = a * i + b;
			y += p.first;
			a += p.first;
			b = y - a * i;
			c = line[loc].second.first;
			d = line[loc].second.second;
			y = c * i + d;
			y += p.second;
			c += p.second;
			d = y - c * i;
			bit.upd(loc, line[loc] - pv);
		}
		for (auto& [l, r, n] : qv[i]) ans[n] = get(r, i) - get(l - 1, i);
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

Compilation message

ho_t5.cpp: In function 'll get(int, int)':
ho_t5.cpp:64:6: warning: unused variable 'ind' [-Wunused-variable]
   64 |  int ind = t * res.first.first + res.first.second;
      |      ^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9688 KB Output is correct
2 Correct 5 ms 9780 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9852 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9784 KB Output is correct
10 Correct 6 ms 9780 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 8 ms 9812 KB Output is correct
14 Correct 5 ms 9760 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9844 KB Output is correct
18 Correct 6 ms 9776 KB Output is correct
19 Correct 5 ms 9812 KB Output is correct
20 Correct 6 ms 9780 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct
23 Correct 6 ms 9776 KB Output is correct
24 Correct 6 ms 9776 KB Output is correct
25 Correct 7 ms 9752 KB Output is correct
26 Correct 5 ms 9812 KB Output is correct
27 Correct 5 ms 9812 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Correct 6 ms 9772 KB Output is correct
30 Correct 5 ms 9812 KB Output is correct
31 Correct 5 ms 9812 KB Output is correct
32 Correct 6 ms 9812 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9688 KB Output is correct
2 Execution timed out 1004 ms 54184 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9688 KB Output is correct
2 Execution timed out 1022 ms 52092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9688 KB Output is correct
2 Correct 5 ms 9780 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9852 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9784 KB Output is correct
10 Correct 6 ms 9780 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 8 ms 9812 KB Output is correct
14 Correct 5 ms 9760 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9844 KB Output is correct
18 Correct 6 ms 9776 KB Output is correct
19 Correct 5 ms 9812 KB Output is correct
20 Correct 6 ms 9780 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct
23 Correct 6 ms 9776 KB Output is correct
24 Correct 6 ms 9776 KB Output is correct
25 Correct 7 ms 9752 KB Output is correct
26 Correct 5 ms 9812 KB Output is correct
27 Correct 5 ms 9812 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Correct 6 ms 9772 KB Output is correct
30 Correct 5 ms 9812 KB Output is correct
31 Correct 5 ms 9812 KB Output is correct
32 Correct 6 ms 9812 KB Output is correct
33 Execution timed out 1004 ms 54184 KB Time limit exceeded
34 Halted 0 ms 0 KB -