Submission #380423

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
380423	2021-03-21T17:04:06 Z	SavicS	Poklon (COCI17_poklon)	C++14	140 / 140	1553 ms	37100 KB

poklon

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 500005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;
ll niz[maxn];

vector<pii> upit[maxn];

int cnt[maxn];
int last[maxn];
int pre[maxn];
int jos[maxn];

int res[maxn];

map<ll,int> ind;

ll dud1[maxn];
void upd1(int x, ll val) {
	while(x <= maxn) {
		dud1[x] += val;
		x += x&(-x);
	}
}
ll query1(int x) {
	ll sum = 0;
	while(x > 0) {
		sum += dud1[x];
		x -= x&(-x);
	}
	return sum;
}

ll dud2[maxn];
void upd2(int x, ll val) {
	while(x <= maxn) {
		dud2[x] += val;
		x += x&(-x);
	}
}
ll query2(int x) {
	ll sum = 0;
	while(x > 0) {
		sum += dud2[x];
		x -= x&(-x);
	}
	return sum;
}

int main() {
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	cin >> n >> q;
	ff(i,1,n) {
		cin >> niz[i];
		ind[niz[i]] = 0;
	}
	int br = 0;
	for(auto& c : ind)c.se = ++br;

	ff(i,1,n)niz[i] = ind[niz[i]];

	ff(i,1,q) {
		int l, r;
		cin >> l >> r;
		upit[r].pb({l, i});
	}

	ff(i,1,n) {
		int x = niz[i];
		cnt[x] += 1;
		if(cnt[x] >= 2) {
			if(pre[x] != 0) {
				upd1(pre[x], -1);
			}
			if(jos[x] != 0) {
				upd2(jos[x], -1);
			}

			upd1(last[x], 1);
			if(pre[x] != 0)upd2(pre[x], 1);

			jos[x] = pre[x];
			pre[x] = last[x];

		}
		last[x] = i;
		for(auto c : upit[i]) {
			int l = c.fi;
			int id = c.se;
			res[id] = query1(i) - query1(l - 1) - (query2(i) - query2(l - 1));
		}
	}
	ff(i,1,q)cout << res[i] << endl;
	return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	12268 KB	Output is correct
2	Correct	10 ms	12268 KB	Output is correct
3	Correct	12 ms	12268 KB	Output is correct
4	Correct	22 ms	12416 KB	Output is correct
5	Correct	288 ms	17132 KB	Output is correct
6	Correct	285 ms	17132 KB	Output is correct
7	Correct	605 ms	22348 KB	Output is correct
8	Correct	927 ms	27116 KB	Output is correct
9	Correct	1250 ms	31980 KB	Output is correct
10	Correct	1553 ms	37100 KB	Output is correct