Submission #821067

#	Time	Username	Problem	Language	Result	Execution time	Memory
821067		vjudge1	Poklon (COCI17_poklon)	C++17	0 / 140	5067 ms	18508 KiB

poklon

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask << (x)) & 1)
#define TASK "task"

using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int Log = sqrt(mxN);
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

struct item {
	int l;
	int r;
	int idx;
	bool operator < (const item & x) {
		if(l / Log == x.l / Log) return r < x.r;
		else return l / Log < x.l / Log;
	}
}q[mxN];

int n;
int queries;
int a[mxN];
int res[mxN];
map<int,int>cnt;

void solve() {
	cin >> n >> queries;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= queries; i++) cin >> q[i].l >> q[i].r,q[i].idx = i;
	sort(q + 1,q + queries + 1);
	int l = q[1].l,r = q[1].r,ans = 0;
	for (int i = q[1].l; i <= q[1].r; i++) {
		cnt[a[i]]++;
		if(cnt[a[i]] == 2) ans++;
		if(cnt[a[i]] == 3) ans--;
	}
	res[q[1].idx] = ans;
	for (int i = 2; i <= queries; i++) {
		while(l > q[i].l) {
			l--;
			if(cnt[a[l]] == 2) ans--;
			cnt[a[l]]++;
			if(cnt[a[l]] == 2) ans++;
		}
		while(l < q[i].l) {
			if(cnt[a[l]] == 2) ans--;
			cnt[a[l]]--;
			l++;
			if(cnt[a[l]] == 2) ans++;
		}
		while(r < q[i].r) {
			r++;
			if(cnt[a[r]] == 2) ans--;
			cnt[a[r]]++;
			if(cnt[a[r]] == 2) ans++;
		}
		while(r > q[i].r) {
			if(cnt[a[r]] == 2) ans--;
			cnt[a[r]]--;
			r--;
			if(cnt[a[r]] == 2) ans++;
		}
		res[q[i].idx] = ans;
	}
	for (int i = 1; i <= queries; i++) cout << res[i] << "\n";
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

• Subtask 1: 0 / 140