oj.uz

Submission #48256

# Submission time Handle Problem Language Result Execution time Memory
48256 2018-05-11T06:36:31 Z DrSwad Poklon (COCI17_poklon) C++11
0 / 140
 5000 ms 52264 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 2296 KB Output isn't correct
2 Incorrect 144 ms 2556 KB Output isn't correct
3 Incorrect 171 ms 2624 KB Output isn't correct
4 Incorrect 831 ms 3812 KB Output isn't correct
5 Execution timed out 5023 ms 14348 KB Time limit exceeded
6 Execution timed out 5034 ms 15780 KB Time limit exceeded
7 Execution timed out 5043 ms 22124 KB Time limit exceeded
8 Execution timed out 5038 ms 30236 KB Time limit exceeded
9 Execution timed out 5023 ms 40796 KB Time limit exceeded
10 Execution timed out 5019 ms 52264 KB Time limit exceeded