제출 #48256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48256		DrSwad	Poklon (COCI17_poklon)	C++11	0 / 140	5043 ms	52264 KiB

poklon

// Implementation practice (Have seen the editorial)
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cerr << #a << ": " << (a) << "\n"
#define RUNTIME prinf("%lf\n",(double)clock()/CLOCKS_PER_SEC);

typedef long long ll;

const int N = int(5e5) + 10;

int n, sq, q;
int a[N];
int cnt[N];
int answer[N];

struct query {
	int id, l, r, ans;
	query() {cin >> l >> r; l--; r--;}
	bool operator < (query& q2) {
		return r < q2.r;
	}
};

vector<query> blk[1000];

int main() {
	/*freopen("out", "w", stdout);
	freopen("in", "r", stdin);*/
	ios::sync_with_stdio(false);cin.tie(NULL);

	cin >> n >> q;
	sq = (int)sqrt(n + 0.5);
	vector<int> tmp(n);
	for (int i = 0; i < n; i++) cin >> a[i], tmp[i] = a[i];
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < n; i++)
		a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin();
	for (int i = 0; i < q; i++) {
		query qq; qq.id = i;
		blk[qq.l/sq].push_back(qq);
	}
	for (int i = 0; i < 1000; i++)
		sort(blk[i].begin(), blk[i].end());

	for (int bi = 0; bi < 1000; bi++) {
		vector<query>& blkq = blk[bi];
		int l = sq*bi, r = sq*bi, qi = 0, totq = blkq.size();
		int ans = 0;
		memset(cnt, 0, sizeof cnt);
		for (; r < n; r++) {
			cnt[a[r]]++;
			if (cnt[a[r]] == 2) ans++;
			if (cnt[a[r]] == 3) ans--;
			while (qi < totq && r == blkq[qi].r) {
				debug(r);
				while (l != blkq[qi].l) {
					debug(l);
					if (l < blkq[qi].l) {
						cnt[a[l]]--;
						if (cnt[a[l]] == 1) ans--;
						else if (cnt[a[l]] == 2) ans++;
						l++;
					}
					else {
						l--;
						cnt[a[l]]++;
						if (cnt[a[l]] == 2) ans++;
						else if (cnt[a[l]] == 3) ans--;
					}
				}
				answer[blkq[qi].id] = ans;
				qi++;
			}
		}
	}
	for (int i = 0; i < q; i++) cout << answer[i] << endl;

	//RUNTIME
	return 0;
}

• Subtask 1: 0 / 140