Submission #18909321


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
#include <string>
#define int long long int
using namespace std;
int power[61] = { 0 };
int N;
vector<pair<pair<int, int>, pair<int, int>>> segtree;
void fill(int v)
{
	if (2 * v + 1 < power[N + 1] - 1)
	{
		fill(2 * v + 1);
		fill(2 * v + 2);
		segtree[v].first.first = segtree[2 * v + 1].first.first + segtree[2 * v + 2].first.first;
		segtree[v].first.second = segtree[2 * v + 1].first.second + segtree[2 * v + 2].first.second;
		segtree[v].second.first = segtree[2 * v + 1].second.first;
		segtree[v].second.second = segtree[2 * v + 2].second.second;
	}
	else
	{
		return;
	}
}
void update(int i, int del)
{
	int curr = i;
	segtree[curr].first.first +=del; //always -1
	segtree[curr].first.second=1;
	while (curr > 0)
	{
		curr = (curr - 1) / 2;
		segtree[curr].first.first += del;
		segtree[curr].first.second = segtree[2*curr+1].first.second+segtree[2*curr+2].first.second;
	}
}
int sum(int l, int r, int v) //SUM OF RANGE
{
	if (segtree[v].second.first >= l && segtree[v].second.second <= r)
	{
		return segtree[v].first.first;
	}
	else if (segtree[v].second.second<l || segtree[v].second.first>r)
	{
		return 0;
	}
	else
	{
		return (sum(l, r, 2 * v + 1) + sum(l, r, 2 * v + 2));
	}
}
int find(int l, int r, int v) //NUMBER OF ZEROES IN RANGE
{
	if (segtree[v].second.first >= l && segtree[v].second.second <= r)
	{
		return segtree[v].first.second;
	}
	else if (segtree[v].second.second<l || segtree[v].second.first>r)
	{
		return 0;
	}
	else
	{
		return (find(l, r, 2 * v + 1) + find(l, r, 2 * v + 2));
	}
}
vector<int> obs[200001]; //obs[j]=vector of all obstacles in row number j
void solve()
{
	int h, w, m;
	cin>>h>>w>>m;
	for (int j=1; j<=m; j++)
	{
		int x, y;
		cin>>x>>y;
		obs[x].push_back(y);
	}
	for (int j = 1; j <= w; j++) sort(obs[j].begin(), obs[j].end());
	///////BUILDING THE SEGMENT TREE: SUM OF RANGE AND NUMBER OF ZEROES IN RANGE
	for (int j = 0; j <= 60; j++)
	{
		if (power[j] >= w+1)
		{
			N = j;
			break;
		}
	}
	segtree.resize(power[N + 1] - 1);	
	for (int j = power[N] - 1; j < power[N + 1] - 1; j++)
	{
		segtree[j].first.first = 1;
		segtree[j].first.second = 0;
		segtree[j].second.first = j - power[N] + 1;
		segtree[j].second.second = j - power[N] + 1;
	}
	fill(0);
	//////END OF BUILDING THE SEGMENT TREE

	if ((int)obs[1].size())
	{
		int w1 = obs[1][0]; //effective width
		for (int j = w1; j <= w; j++)
		{
			update(j + power[N] - 1, -1);
		}
	}

	int ans=0;
	bool ryt=1; //can we reach row j from (1, 1) in one move?
	for (int j=1; j<=h; j++)
	{
		if ((int)obs[j].size())
		{
			if (obs[j][0]==1)
			{
				ryt=0;
			}
		}
		for (auto i:obs[j])
		{
			if (segtree[i + power[N] - 1].first.first)
			{
				update(i + power[N] - 1, -1);
			}
		}
		ans+=sum(1, w, 0);
		if (ryt)
		{
			if ((int)obs[j].size())
			{
				ans+=find(1, obs[j][0]-1, 0);
			}
			else
			{
				ans+=find(1, w, 0);
			}
		}		
	}
	cout<<ans<<"\n";
	return;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	//cin >> t;
	t=1;
	power[0] = 1;
	for (int j = 1; j <= 60; j++) power[j] = power[j - 1] * 2;
	while (t--)
	{
		solve();
	}
	return 0;
}

Submission Info

Submission Time
Task F - Rook on Grid
User mshiladityam
Language C++ (GCC 9.2.1)
Score 600
Code Size 3460 Byte
Status AC
Exec Time 190 ms
Memory 28520 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 29
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 85 ms 24196 KB
hand_02.txt AC 84 ms 24192 KB
hand_03.txt AC 32 ms 24284 KB
hand_04.txt AC 11 ms 8204 KB
hand_05.txt AC 6 ms 8236 KB
hand_06.txt AC 10 ms 8264 KB
random_01.txt AC 190 ms 28460 KB
random_02.txt AC 139 ms 28408 KB
random_03.txt AC 189 ms 28520 KB
random_04.txt AC 189 ms 28516 KB
random_05.txt AC 149 ms 28512 KB
random_06.txt AC 176 ms 28396 KB
random_07.txt AC 168 ms 28412 KB
random_08.txt AC 85 ms 24224 KB
random_09.txt AC 85 ms 24168 KB
random_10.txt AC 84 ms 24228 KB
random_11.txt AC 45 ms 9968 KB
random_12.txt AC 39 ms 10032 KB
random_13.txt AC 42 ms 9940 KB
random_14.txt AC 45 ms 10032 KB
random_15.txt AC 45 ms 9872 KB
random_16.txt AC 45 ms 9968 KB
random_17.txt AC 45 ms 9932 KB
random_18.txt AC 10 ms 8280 KB
random_19.txt AC 9 ms 8352 KB
random_20.txt AC 7 ms 8352 KB
sample_01.txt AC 5 ms 8164 KB
sample_02.txt AC 9 ms 8284 KB
sample_03.txt AC 86 ms 24128 KB