Contest Duration: - (local time) (100 minutes) Back to Home

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 2020-12-20 20:24:38+0900 F - Rook on Grid mshiladityam C++ (GCC 9.2.1) 600 3460 Byte AC 190 ms 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