Submission #48257

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48257	2018-05-11T06:39:54 Z	DrSwad	Poklon (COCI17_poklon)	C++11	140 / 140	1390 ms	20848 KB

poklon

// Implementation practice (Have seen the editorial)
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #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() {scanf("%d %d", &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);

	scanf("%d %d", &n, &q);
	sq = (int)sqrt(n + 0.5);
	vector<int> tmp(n);
	for (int i = 0; i < n; i++) scanf("%d", 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) {
				while (l != blkq[qi].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++) printf("%d\n", answer[i]);

	//RUNTIME
	return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:34:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; i++) scanf("%d", a+i), tmp[i] = a[i];
                              ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
poklon.cpp: In constructor 'query::query()':
poklon.cpp:18:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  query() {scanf("%d %d", &l, &r); l--; r--;}
           ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	2296 KB	Output is correct
2	Correct	101 ms	2532 KB	Output is correct
3	Correct	101 ms	2532 KB	Output is correct
4	Correct	106 ms	2776 KB	Output is correct
5	Correct	233 ms	6308 KB	Output is correct
6	Correct	234 ms	6308 KB	Output is correct
7	Correct	466 ms	9948 KB	Output is correct
8	Correct	758 ms	13400 KB	Output is correct
9	Correct	1052 ms	17248 KB	Output is correct
10	Correct	1390 ms	20848 KB	Output is correct