oj.uz

Submission #238652

# Submission time Handle Problem Language Result Execution time Memory
238652 2020-06-12T09:03:56 Z MrRobot_28 Dojave (COCI17_dojave) C++17
112 / 140
 4000 ms 106936 KB 
#include<bits/stdc++.h>
using namespace std;
int tree[4][(1 << 21)], treecnt[4][(1 << 21)], upd[4][(1 << 21)];
inline void push(int ind, int v, int l, int r)
{
	tree[ind][v * 2] += upd[ind][v];
	tree[ind][v * 2 + 1] += upd[ind][v];
	upd[ind][v * 2] += upd[ind][v];
	upd[ind][v * 2 + 1] += upd[ind][v];
	upd[ind][v] = 0;
}
inline void update(int ind, int v, int l, int r, int al, int ar, int val)
{
	if(l >= al && r <= ar)
	{
		tree[ind][v] += val;
		upd[ind][v] += val;
	}
	else if(l <= ar && r >= al)
	{
		push(ind, v, l, r);
		if(al <= (r + l) / 2)
		{
		update(ind, v * 2, l, (r + l) / 2, al, ar, val);
		}
		if(ar > (r + l) / 2)
		{
		update(ind, v * 2 + 1, (r + l) / 2 + 1, r, al, ar, val);
		}
		if(tree[ind][v * 2] == tree[ind][v * 2 + 1])
		{
			tree[ind][v] = tree[ind][v * 2];
			treecnt[ind][v] = treecnt[ind][v * 2] + treecnt[ind][v * 2 + 1];
		}
		else if(tree[ind][v * 2] < tree[ind][v * 2 + 1])
		{
			tree[ind][v] = tree[ind][v * 2];
			treecnt[ind][v] = treecnt[ind][v * 2];
			 
		}
		else
		{
			tree[ind][v] = tree[ind][v * 2 + 1];
			treecnt[ind][v] = treecnt[ind][v * 2 + 1];
		}
	}
}
inline pair <int, int> ans(int ind, int v, int l, int r, int al, int ar){
	if(l >= al && r <= ar)
	{
		return {tree[ind][v], treecnt[ind][v]};
	}
	else if(l <= ar && r >= al)
	{
		push(ind, v, l ,r);
		if(ar <= (r + l) / 2)
		{
			return ans(ind, v * 2, l, (r + l) / 2, al, ar);
		}
		if(al > (r + l) / 2)
		{
			return ans(ind, v * 2 + 1, (r + l) / 2 + 1, r, al, ar);
		}
		pair <int, int> v1 = ans(ind, v * 2, l, (r + l) / 2, al, ar);
		pair <int, int> v2 = ans(ind, v * 2 + 1, (r + l) / 2 + 1, r, al, ar);
		if(v1.first == v2.first)
		{
			return {v1.first, v1.second + v2.second};
		}
		else if(v1.first < v2.first){
			return v1;
		}
		else
		{
			return v2;
		}
	}
	else
	{
		return {1e9, 0};
	}
}
void build(int ind, int v, int l, int r)
{
	if(l == r){
		treecnt[ind][v] = 1;
		if(l % 4 == ind){
			tree[ind][v] = 0;
		}
		else
		{
			tree[ind][v] = 1e9;
		}
		return;
	}
	build(ind, v * 2, l, (r + l) / 2);
	build(ind, v * 2 + 1, (r + l) / 2 + 1, r);
	tree[ind][v] = min(tree[ind][v * 2], tree[ind][v * 2 + 1]);
	if(tree[ind][v * 2] == tree[ind][v * 2 + 1])
		{
			tree[ind][v] = tree[ind][v * 2];
			treecnt[ind][v] = treecnt[ind][v * 2] + treecnt[ind][v * 2 + 1];
		}
		else if(tree[ind][v * 2] < tree[ind][v * 2 + 1])
		{
			tree[ind][v] = tree[ind][v * 2];
			treecnt[ind][v] = treecnt[ind][v * 2];
			 
		}
		else
		{
			tree[ind][v] = tree[ind][v * 2 + 1];
			treecnt[ind][v] = treecnt[ind][v * 2 + 1];
		}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	int m = pow(2, n);
	vector <int> A(m);
	vector <int> ind(m, -1);
	for(int i = 0; i < m; i++)
	{
		cin >> A[i];
		ind[A[i]] = i;
	}
	long long sum = 0;
	for(int i= 0; i < 4; i++)
	{
		build(i, 1, 0, m - 1);
	}
	if(m == 2)
	{
		sum++;
	}
	for(int i = m - 1; i >= 0; i--)
	{
		if(ind[m - 1 - A[i]] > i)
		{
			for(int j = 0; j < 4; j++)
			{
				update(j, 1, 0, m - 1, ind[m - 1 - A[i]], m - 1, -2);
			}
		}
		for(int j = 0; j < 4; j++)
		{
			update(j, 1, 0, m - 1, i, m - 1, 1);
		}
		pair <int, int> v = ans((i + 3) % 4, 1, 0, m - 1, i, m - 1);
		if(v.first == 0)
		{
			sum += v.second;
		}
	}
	sum = 1LL * (m + 1) * m / 2 - sum;
	cout << sum;
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 896 KB Output is correct
2 Correct 11 ms 896 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1280 KB Output is correct
2 Correct 19 ms 1280 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2296 KB Output is correct
2 Correct 38 ms 2172 KB Output is correct
3 Correct 40 ms 2168 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 7544 KB Output is correct
2 Correct 176 ms 7544 KB Output is correct
3 Correct 363 ms 14456 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 7544 KB Output is correct
2 Correct 379 ms 14372 KB Output is correct
3 Correct 814 ms 27768 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 27616 KB Output is correct
2 Correct 771 ms 27768 KB Output is correct
3 Correct 769 ms 27720 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 106936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 106920 KB Time limit exceeded
2 Halted 0 ms 0 KB -