Submission #55661

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55661	2018-07-08T11:56:06 Z	polyfish	Poklon (COCI17_poklon)	C++14	140 / 140	1346 ms	69636 KB

poklon

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 500002;

class range_tree {
public:
	vector<pair<int, int> > st;
	int n;

	range_tree(int _n) {
		n = _n;
		st.resize(4*n, make_pair(0, 0));
	}

	void down(int id) {
		int tmp = st[id].second;
		st[id].second = 0;
		st[id*2].first += tmp;
		st[id*2].second += tmp;
		st[id*2+1].first += tmp;
		st[id*2+1].second += tmp;
	}

	void upd(int u, int v, int val, int l, int r, int id) {
		if (v<l || u>r)
			return;
		if (u<=l && r<=v) {
			st[id].first += val;
			st[id].second += val;
			return;
		}
		down(id);
		int mid = (l + r) / 2;
		upd(u, v, val, l, mid, id*2);
		upd(u, v, val, mid+1, r, id*2+1);
		st[id].first = st[id*2].first + st[id*2+1].first;
	}

	int get(int pos, int l, int r, int id) {
		if (pos<l || pos>r)
			return 0;
		if (pos==l && r==pos)
			return st[id].first;
		down(id);
		int mid = (l + r) / 2;
		return get(pos, l, mid, id*2) + get(pos, mid+1, r, id*2+1);
	}

	void upd(int u, int v, int val) {
		upd(u, v, val, 1, n, 1);
	}

	int get(int pos) {
		return get(pos, 1, n, 1);
	}
};

struct query {
	int L, R, id;

	bool operator<(const query &x) {
		return L<x.L;
	}
};

int n, nQuery, a[MAX_N], L1[MAX_N], R1[MAX_N], L2[MAX_N], R2[MAX_N], res[MAX_N];
query q[MAX_N];

void enter() {
	cin >> n >> nQuery;
	for (int i=1; i<=n; ++i)
		cin >> a[i];
	for (int i=1; i<=nQuery; ++i) {
		cin >> q[i].L >> q[i].R;
		q[i].id = i;
	}
}

void init() {
	map<int, int> pos;
	for (int i=1; i<=n; ++i) {
		L1[i] = pos[a[i]];
		L2[i] = L1[L1[i]];
		pos[a[i]] = i;
	}
	pos.clear();
	for (int i=n; i>=1; --i) {
		R1[i] = pos[a[i]];
		R2[i] = R1[R1[i]];
		pos[a[i]] = i;
	}
	for (int i=1; i<=n; ++i) {
		if (R1[i]==0)
			R1[i] = n + 1;
		if (R2[i]==0)
			R2[i] = n + 1;
	}
	sort(q+1, q+nQuery+1);
}

void solve(int L[], int R[], int add_val) {
	vector<pair<int, int> > b;
	range_tree tr(n);
	for (int i=1; i<=n; ++i)
		b.push_back(make_pair(L[i], i));
	sort(b.begin(), b.end());
	int head = -1;
	// for (int i=0; i<b.size(); ++i)
	// 	cerr << b[i].first << ' ' << b[i].second << '\n';
	for (int i=1; i<=nQuery; ++i) {
		while (head+1<b.size() && b[head+1].first<q[i].L) {
			++head;
			int id = b[head].second;
			tr.upd(id, R[id]-1, add_val);
		}
		//debug(head);
		res[q[i].id] += tr.get(q[i].R);
	}
}

void print_result() {
	for (int i=1; i<=nQuery; ++i)
		cout << res[i] << '\n';
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	init();
	solve(L2, R1, 1);
	solve(L1, R1, -1);
	print_result();
}

Compilation message

poklon.cpp: In function 'void solve(int*, int*, int)':
poklon.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<b.size() && b[head+1].first<q[i].L) {
          ~~~~~~^~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	528 KB	Output is correct
3	Correct	6 ms	552 KB	Output is correct
4	Correct	10 ms	1004 KB	Output is correct
5	Correct	202 ms	10752 KB	Output is correct
6	Correct	206 ms	12256 KB	Output is correct
7	Correct	583 ms	24308 KB	Output is correct
8	Correct	981 ms	39084 KB	Output is correct
9	Correct	1346 ms	53536 KB	Output is correct
10	Correct	1337 ms	69636 KB	Output is correct