oj.uz

Submission #535794

# Submission time Handle Problem Language Result Execution time Memory
535794 2022-03-11T08:42:11 Z abc864197532 Fire (JOI20_ho_t5) C++17
6 / 100
 146 ms 12716 KB 
 #include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l)
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif
const int N = 200005;

int bit[N];

void add(int p, int v) {
	for (p += 2; p < N; p += p & (-p))
		bit[p] += v;
}

int query(int p) {
	int ans = 0;
	for (p += 2; p > 0; p -= p & (-p))
		ans += bit[p];
	return ans;
}

int main () {
	owo;
	int n, q;
	cin >> n >> q;
	vector <int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	vector <int> pre(n, n + 1);
	for (int i = 0; i < n; ++i) {
		if (a[i] == 2)
			pre[i] = 0;
		else if (i) {
			pre[i] = pre[i - 1] + 1;
		}
	}
	vector <array <int, 4>> queries;
	for (int i = 0, t, l, r; i < q; ++i) {
		cin >> t >> l >> r, --l, t++;
		queries.pb({t, l, r, i});
	}
	sort(rall(queries));
	vector <int> ans(q);
	vector <int> p(n);
	iota(all(p), 0);
	sort(all(p), [&](int i, int j) {
		return pre[i] > pre[j];
	});
	int now = 0;
	for (auto i : queries) {
		while (now < n && pre[p[now]] >= i[0]) {
			add(p[now] + 1, 1);
			now++;
		}
		ans[i[3]] = 2 * (i[2] - i[1]) - (query(i[2]) - query(i[1]));
	}
	for (int i : ans)
		cout << i << '\n';
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8248 KB Output is correct
2 Correct 128 ms 12368 KB Output is correct
3 Correct 123 ms 12604 KB Output is correct
4 Correct 137 ms 12576 KB Output is correct
5 Correct 121 ms 12584 KB Output is correct
6 Correct 127 ms 12348 KB Output is correct
7 Correct 120 ms 12448 KB Output is correct
8 Correct 109 ms 12488 KB Output is correct
9 Correct 124 ms 12612 KB Output is correct
10 Correct 146 ms 12392 KB Output is correct
11 Correct 116 ms 12716 KB Output is correct
12 Correct 125 ms 12612 KB Output is correct
13 Correct 133 ms 12532 KB Output is correct
14 Correct 117 ms 12600 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -