oj.uz

Submission #56814

# Submission time Handle Problem Language Result Execution time Memory
56814 2018-07-12T16:18:29 Z polyfish Dojave (COCI17_dojave) C++14
140 / 140
 869 ms 66400 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 = 1100002;

struct query {
	int l, r, val;

	query() {}
	query(int l, int r, int val): 
		l(l), r(r), val(val) {}

	bool operator<(const query & Q) {
		return val<Q.val;
	}
};

struct fenwick_tree {
	vector<int> bit;
	int n;

	void init(int _n) {
		n = _n;
		bit.resize(n+1, 0);
	}

	void upd(int id) {
		for (; id<=n; id += id & (-id))
			++bit[id];
	}

	int get(int id) {
		if (id==0)
			return 0;
		int res = 0;
		for (; id>0; id -= id & (-id))
			res += bit[id];
		return res;
	}

	int get(int l, int r) {
		if (l>r)
			return 0;
		return get(r) - get(l-1);
	}
};

int m, n, a[MAX_N], pos[MAX_N], L[MAX_N], R[MAX_N];
vector<pair<int, int> > seg;
vector<query> q;

void enter() {
	cin >> m;
	n = 1 << m;
	for (int i=0; i<n; ++i)
		cin >> a[i];
}

void init() {
	// debug(n);
	for (int i=0; i<n; ++i)
		pos[a[i]] = i;
	for (int i=0; i<n; ++i) {
		if (pos[(n-1)^a[i]]<i)
		seg.push_back(make_pair(pos[(n-1)^a[i]], i));
	}
	// for (int i=0; i<seg.size(); ++i)
	// 	cerr << seg[i].first << ' ' << seg[i].second << '\n';
}

void make_L() {
	sort(seg.begin(), seg.end());
	int head = -1;
	priority_queue<int, vector<int>, greater<int> > pq;
	for (int i=0; i<n; ++i) {
		while (head+1<seg.size() && seg[head+1].first<i) {
			++head;
			pq.push(seg[head].second);
		}
		int x = n;
		while (pq.size()) {
			int tmp = pq.top();
			if (tmp>=i) {
				x = tmp;
				break;
			}
			pq.pop();
		}
		// debug(x);
		L[i] = x - 1;
	}
	//PR0(L, n);
}

void make_R() {
	sort(seg.begin(), seg.end(), [](pair<int, int> a, pair<int, int> b) {
		return a.second>b.second;
	});
	int head = -1;
	priority_queue<int> pq;
	for (int i=n-1; i>=0; --i) {
		while (head+1<seg.size() && seg[head+1].second>i) {
			++head;
			pq.push(seg[head].first);
		}
		int x = -1;
		while (pq.size()) {
			int tmp = pq.top();
			if (tmp<=i) {
				x = tmp;
				break;
			}
			pq.pop();
		}
		R[i] = x+1;
	}
	//PR0(R, n);
}

void make_query() {
	for (int i=0; i<n; ++i) {
		q.push_back(query(i, L[i], i));
	}
	sort(q.begin(), q.end());
	// for (int i=0; i<q.size(); ++i)
	// 	cerr << q[i].l << ' ' << q[i].r << ' ' << q[i].val << '\n';
}

int64_t solve_query() {
	if (m==1)
		return 2;
	vector<pair<int, int> > b;
	fenwick_tree tr[4];
	for (int i=0; i<4; ++i)
		tr[i].init(n);
	int64_t res = 0;
	for (int i=0; i<n; ++i)
		b.push_back(make_pair(R[i], i));
	sort(b.begin(), b.end());
	int head = -1;
	for (int i=0; i<q.size(); ++i) {
		int l = q[i].l, r = q[i].r, val = q[i].val;
		while (head+1<b.size() && b[head+1].first<=val) {
			++head;
			// if (l==0)
			// 	debug((b[head].second+1)%4);
			tr[(b[head].second+1)%4].upd(b[head].second + 1);
		}
		res += tr[l%4].get(l+1, r+1);
	}
	return 1LL * n * (n + 1) / 2 - res;
}

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();
	make_L();
	make_R();
	make_query();
	cout << solve_query();
}

Compilation message

dojave.cpp: In function 'void make_L()':
dojave.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<seg.size() && seg[head+1].first<i) {
          ~~~~~~^~~~~~~~~~~
dojave.cpp: In function 'void make_R()':
dojave.cpp:110:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<seg.size() && seg[head+1].second>i) {
          ~~~~~~^~~~~~~~~~~
dojave.cpp: In function 'int64_t solve_query()':
dojave.cpp:149:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<q.size(); ++i) {
                ~^~~~~~~~~
dojave.cpp:151:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<b.size() && b[head+1].first<=val) {
          ~~~~~~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 524 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 812 KB Output is correct
2 Correct 4 ms 812 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1088 KB Output is correct
2 Correct 6 ms 1088 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1584 KB Output is correct
2 Correct 10 ms 1584 KB Output is correct
3 Correct 8 ms 1768 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4720 KB Output is correct
2 Correct 38 ms 4720 KB Output is correct
3 Correct 50 ms 8812 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8812 KB Output is correct
2 Correct 78 ms 8812 KB Output is correct
3 Correct 121 ms 17000 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 17120 KB Output is correct
2 Correct 154 ms 17120 KB Output is correct
3 Correct 122 ms 17120 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 66376 KB Output is correct
2 Correct 856 ms 66380 KB Output is correct
3 Correct 357 ms 66400 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 66400 KB Output is correct
2 Correct 583 ms 66400 KB Output is correct
3 Correct 421 ms 66400 KB Output is correct
4 Correct 822 ms 66400 KB Output is correct