Submission #238622

#	Time	Username	Problem	Language	Result	Execution time	Memory
238622		MrRobot_28	Dojave (COCI17_dojave)	C++17	112 / 140	4090 ms	105144 KiB

dojave

#include<bits/stdc++.h>
using namespace std;
int tree[4][(1 << 21)], treecnt[4][(1 << 21)], upd[4][(1 << 21)];
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;
}
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];
		}
	}
}
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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14