oj.uz

Submission #818107

# Submission time Handle Problem Language Result Execution time Memory
818107 2023-08-10T02:18:57 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 301 ms 32784 KB 
#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 5e5 + 7;

int n, q;
int a[N], ans[N], last1[N], last2[N], bit[N];
vector <int> value;
vector <pair <int, int>> queries[N];

struct FenwickTree {
	void update(int i, int value) {
		for (; i <= n; i += i & -i) bit[i] += value;
	}

	int get(int i) {
		int res = 0;
		for (; i; i -= i & -i) res += bit[i];
		return res;
	}

	int query(int l, int r) {
		return get(r) - get(l - 1);
	}
} ft;

void add(int index, int value) {
	if (last2[index] != 0) {
		ft.update(last2[index], value);
		if (last2[last2[index]] != 0) {
			ft.update(last2[last2[index]], -value);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		value.emplace_back(a[i]);
	}

	sort(all(value));
	value.erase(unique(all(value)), value.end());

	for (int i = 1; i <= n; ++i) a[i] = lower_bound(all(value), a[i]) - value.begin() + 1;
 
	for (int i = 1; i <= q; ++i) {
		int l, r; cin >> l >> r;
		queries[l].emplace_back(r, i);
	}

	for (int i = n; i >= 1; --i) {
		if (last1[a[i]]) add(last1[a[i]], -1);
		last2[i] = last1[a[i]];
		last1[a[i]] = i;
		add(i, 1);

		for (auto [r, idx] : queries[i]) {
			ans[idx] = ft.query(i, r);
		}
	}

	for (int i = 1; i <= q; ++i) cout << ans[i] << ' ';
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 8 ms 12284 KB Output is correct
5 Correct 50 ms 16148 KB Output is correct
6 Correct 53 ms 16124 KB Output is correct
7 Correct 110 ms 20312 KB Output is correct
8 Correct 179 ms 24496 KB Output is correct
9 Correct 248 ms 28560 KB Output is correct
10 Correct 301 ms 32784 KB Output is correct