oj.uz

Submission #736164

# Submission time Handle Problem Language Result Execution time Memory
736164 2023-05-05T09:12:46 Z marvinthang Poklon (COCI17_poklon) C++17
140 / 140
 1546 ms 21460 KB 
/******************************
*    author : @marvinthang    *
*    date : 02 / 03 / 2021    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false);\
                     cin.tie(NULL);\
                     //cout.tie(NULL);
#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);

const     double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const      int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const  long long oo = 1e9;
const       int MAX = 5e5 + 5;
const int BLOCK_SIZE = 700;

#define getBlock(i) ((i) - 1) / BLOCK_SIZE + 1
#define getLeft(id) ((id) - 1) * BLOCK_SIZE + 1
#define getRight(id) (id) * BLOCK_SIZE

int N, Q, A[MAX], pos[MAX], cnt[MAX];

struct Query {
	int l, r, id;
	Query(int _l = 0, int _r = 0, int _id = 0):
		l(_l), r(_r), id(_id) {};
		bool operator < (const Query &other) const {
			return make_pair(getBlock(l), r) < make_pair(getBlock(other.l), other.r);
		}
};

int ANS[MAX], res;

void add(int id) {
	++cnt[A[id]];
	if (cnt[A[id]] == 3) --res;
	if (cnt[A[id]] == 2) ++res;
}

void del(int id) {
	--cnt[A[id]];
	if (cnt[A[id]] == 1) --res;
	if (cnt[A[id]] == 2) ++res;
}

Query q[MAX];

int main() {
    superspeed;
	cin >> N >> Q;
	for (int i = 1; i <= N; ++i) cin >> A[i], pos[i] = i;
	sort(pos + 1, pos + 1 + N, [&](int a, int b) { return A[a] < A[b]; });
	int last = -oo, cnt = 0;
	for (int i = 1; i <= N; ++i) {
		if (A[pos[i]] > last) ++cnt;
		last = A[pos[i]];
		A[pos[i]] = cnt;
	}
	for (int i = 1; i <= Q; ++i) {
		int l, r; cin >> l >> r;
		q[i] = Query(l, r, i);
	}
	sort(q + 1, q + 1 + Q);
	int curL = 1, curR = 0;
	for (int i = 1; i <= Q; ++i) {
		int l = q[i].l, r = q[i].r;
		while (curL > l) add(--curL);
		while (curR < r) add(++curR);
		while (curL < l) del(curL++);
		while (curR > r) del(curR--);
		ANS[q[i].id] = res;
	}
	for (int i = 1; i <= Q; ++i) cout << ANS[i] << '\n';
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 4 ms 6228 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 9 ms 6344 KB Output is correct
5 Correct 150 ms 8888 KB Output is correct
6 Correct 148 ms 8936 KB Output is correct
7 Correct 388 ms 12220 KB Output is correct
8 Correct 721 ms 15324 KB Output is correct
9 Correct 1096 ms 18528 KB Output is correct
10 Correct 1546 ms 21460 KB Output is correct