Submission #1126932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126932		Zbyszek99	Road Service 2 (JOI24_ho_t5)	C++20	53 / 100	1649 ms	429788 KiB

Main

#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;
        bool is_ok = true;
        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);
                if(nxt.dist == -1) 
                {
                    is_ok = false;
                    break;
                }
                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]);
            }
        }
        if(is_ok)
        cout << ans << "\n";
        else
        cout << "-1\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 0 / 15
• Subtask 4: 11 / 11
• Subtask 5: 0 / 6
• Subtask 6: 0 / 12
• Subtask 7: 26 / 26
• Subtask 8: 0 / 14