oj.uz

답안 #55661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55661 2018-07-08T11:56:06 Z polyfish Poklon (COCI17_poklon) C++14
140 / 140
 1346 ms 69636 KB 
//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

# 결과 실행 시간 메모리 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