oj.uz

Submission #238238

# Submission time Handle Problem Language Result Execution time Memory
238238 2020-06-10T10:39:59 Z MrRobot_28 Dojave (COCI17_dojave) C++17
42 / 140
 1201 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector <vector <int> > tree, treecnt, upd;
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);
		update(ind, v * 2, l, (r + l) / 2, al, ar, val);
		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);
		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);
	int w1 = 0, w2 = 0;
	for(int i = 0; i < m; i++)
	{
		cin >> A[i];
		ind[A[i]] = i;
		w1 = w1 ^ A[i];
		w2 = w2 ^ A[i];
	}
	tree.resize(4, vector <int> (4 * m, 0));
	treecnt.resize(4, vector <int> (4 * m, 0));
	upd.resize(4, vector <int> (4 * m, 0));
	int sum = 0;
	for(int i= 0; i < 4; i++)
	{
		build(i, 1, 0, m - 1);
	}
	w1 ^= A[0];
	w2 ^= A[m - 1];
	if(w1 == m - 1)
	{
		sum++;
	}
	if(w2 == m - 1)
	{
		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 = (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 4 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 384 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2044 KB Output is correct
2 Incorrect 15 ms 2172 KB Output isn't correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3836 KB Output is correct
2 Correct 26 ms 3836 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 7352 KB Output is correct
2 Incorrect 55 ms 7292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 28148 KB Output is correct
2 Incorrect 228 ms 28276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 28120 KB Output is correct
2 Incorrect 533 ms 55824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 111228 KB Output is correct
2 Incorrect 1108 ms 111232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 314 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -