oj.uz

답안 #238239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238239 2020-06-10T10:41:46 Z MrRobot_28 Dojave (COCI17_dojave) C++17
112 / 140
 1213 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);
	for(int i = 0; i < m; i++)
	{
		cin >> A[i];
		ind[A[i]] = 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);
	}
	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 = (m + 1) * m / 2 - sum;
	cout << sum;
    return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2044 KB Output is correct
2 Correct 14 ms 2044 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 3836 KB Output is correct
2 Correct 27 ms 3836 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 7292 KB Output is correct
2 Correct 61 ms 7292 KB Output is correct
3 Correct 52 ms 7292 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 28148 KB Output is correct
2 Correct 228 ms 28156 KB Output is correct
3 Correct 533 ms 55896 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 28156 KB Output is correct
2 Correct 496 ms 55920 KB Output is correct
3 Correct 1020 ms 111312 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1213 ms 111336 KB Output is correct
2 Correct 1078 ms 111340 KB Output is correct
3 Correct 1046 ms 111208 KB Output is correct

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 303 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 324 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -