#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct next_ans
{
int v,dist,pop;
};
vi graph[1000'001];
int comp[1000'001];
int y_index[1000'001];
int real_seg[1000'001];
int cost[1000'001];
vector<pair<pii,int>> seg2;
pii seg[1000'001];
int best_seg[1000'001];
int pref[1000'001];
set<int> cost1;
set<int> cost2;
int m;
struct jump_str
{
int j0,j1,j2;
int dist = 0;
};
jump_str jump[1000'001][20];
jump_str merge_jumps(jump_str s1, int P)
{
if(s1.dist == 0) return jump[s1.j0][P];
jump_str ans;
ans.dist = s1.dist + (1 << P);
ans.j0 = max(jump[s1.j0][P].j1,jump[s1.j1][P].j0);
ans.j1 = max(jump[s1.j0][P].j2,jump[s1.j1][P].j1);
ans.j2 = max(jump[s1.j1][P].j2,jump[s1.j2][P].j1);
return ans;
}
pii dfs(int v)
{
// cout << v << " dfs\n";
comp[v] = m;
pii s = {y_index[v],y_index[v]};
forall(it,graph[v])
{
if(comp[it] == -1)
{
pii s2 = dfs(it);
s.ff = min(s.ff,s2.ff);
s.ss = max(s.ss,s2.ss);
}
}
return s;
}
next_ans find_next(int v, int doc, int pop_cut)
{
if(pop_cut >= seg[doc].ff && pop_cut <= seg[doc].ss)
{
return {max(v,doc),0,pop_cut};
}
if(v == doc) return {v,0,-1};
jump_str cur_jump = {v,v,v,0};
// cout << jump[v][0].j0 << " " << jump[v][0].j1 << " " << jump[v][0].j2 << " " << v << " jump\n";
for(int bit = 19; bit >= 0; bit--)
{
jump_str new_jump = merge_jumps(cur_jump,bit);
// cout << bit << " " << new_jump.j1 << " " << seg[new_jump.j1].ff << " " << seg[new_jump.j1].ss << " next\n";
if(seg[new_jump.j1].ss < seg[doc].ff)
{
// cout << "ok\n";
cur_jump = new_jump;
}
}
// cout << seg[cur_jump.j1].ff << " " << seg[cur_jump.j1].ss << " " << seg[doc].ff << " " << cur_jump.j1 << " segs\n";
if(seg[cur_jump.j1].ss < seg[doc].ff)
{
cur_jump = merge_jumps(cur_jump,0);
}
if(seg[cur_jump.j1].ss < seg[doc].ff)
{
return {-1,-1};
}
v = cur_jump.j1;
//cout << v << " " << doc << " vdoc\n";
pii collide = {max(seg[doc].ff,seg[v].ff),min(seg[doc].ss,seg[v].ss)};
// cout << collide.ff << " " << collide.ss << " collide\n";
if(pref[collide.ss+1] - pref[collide.ff] != 0)
{
auto it = cost1.upper_bound(collide.ss);
it--;
return {max(v,doc),cur_jump.dist+1,*it};
}
auto it = cost2.upper_bound(collide.ss);
it--;
return {max(v,doc),cur_jump.dist+2,*it};
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
ll W,H,q;
cin >> H >> W >> q;
rep(i,H)
{
rep(j,W)
{
int cell = i*W+j;
y_index[cell] = i;
comp[cell] = -1;
}
}
rep(i,H)
{
rep(j,W-1)
{
int cell = i*W+j;
char z;
cin >> z;
if(z == '1')
{
graph[cell].pb(cell+1);
graph[cell+1].pb(cell);
}
}
}
rep(i,H-1)
{
rep(j,W)
{
int cell = i*W+j;
char z;
cin >> z;
if(z == '1')
{
graph[cell].pb(cell+W);
graph[cell+W].pb(cell);
}
}
}
rep(i,H) cin >> cost[i];
rep(i,H)
{
pref[i+1] = pref[i];
if(cost[i] == 1)
pref[i+1]++;
}
rep(i,H*W)
{
if(comp[i] == -1)
{
pii s = dfs(i);
// cout << i << " new\n";
seg2.pb({{s.ss,s.ff},m});
m++;
}
}
sort(all(seg2));
rep(i,m)
{
seg[i] = {seg2[i].ff.ss,seg2[i].ff.ff};
real_seg[seg2[i].ss] = i;
//cout << seg[i].ff << " " << seg[i].ss << " " << seg2[i].ss << " " << i << " seg\n";
}
multiset<int> multi;
vector<pii> events;
rep(i,m)
{
events.pb({seg[i].ff,i});
events.pb({seg[i].ss+1,i+m});
}
sort(all(events));
int cur_event = 0;
rep(i,H)
{
while(cur_event != siz(events) && events[cur_event].ff == i)
{
if(events[cur_event].ss < m)
{
multi.insert(events[cur_event].ss);
}
else
{
multi.erase(multi.find(events[cur_event].ss-m));
}
cur_event++;
}
auto it = multi.end();
if(it != multi.begin())
{
it--;
best_seg[i] = *it ;
}
if(cost[i] == 1) cost1.insert(i);
else cost2.insert(i);
}
rep(i,m)
{
//cost 0
jump[i][0].j0 = i;
jump[i][0].j1 = i;
jump[i][0].j2 = i;
jump[i][0].dist = 1;
//cost 1
auto it = cost1.upper_bound(seg[i].ss);
if(it != cost1.begin())
{
it--;
int v = *it;
if(!(v < seg[i].ff))
{
jump[i][0].j1 = best_seg[v];
}
}
//cost 2
it = cost2.upper_bound(seg[i].ss);
if(it != cost2.begin())
{
it--;
int v = *it;
if(!(v < seg[i].ff))
{
jump[i][0].j2 = best_seg[v];
}
}
}
rep(i,m)
{
jump[i][0].j2 = max(jump[i][0].j2,jump[jump[i][0].j1][0].j1);
}
rep2(bit,1,19)
{
rep(i,m)
{
jump[i][bit] = merge_jumps(jump[i][bit-1],bit-1);
}
}
rep(qq,q)
{
int t;
cin >> t;
vector<pii> points;
rep(j,t)
{
int y,x;
cin >> y >> x;
y--;
x--;
int cell = y*W + x;
// cout << cell << " " << comp[cell] << " " << real_seg[comp[cell]] << " comp\n";
points.pb({seg[real_seg[comp[cell]]].ff,real_seg[comp[cell]]});
}
sort(all(points));
int pop_cut = -1;
int pop_v = -1;
int ans = 0;
forall(it,points)
{
// cout << seg[pop_v].ff << " " << seg[pop_v].ss << " " << pop_cut << " " << ans << "\n";
int v = it.ss;
if(pop_v == -1)
{
pop_v = v;
}
else
{
next_ans nxt = find_next(pop_v,v,pop_cut);
ans += nxt.dist;
pop_v = nxt.v;
pop_cut = max(pop_cut,nxt.pop);
if(pop_cut != -1) pop_v = max(pop_v,best_seg[pop_cut]);
}
}
cout << ans << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |