제출 #1181293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181293		Zbyszek99	Road Service 2 (JOI24_ho_t5)	C++20	86 / 100	1835 ms	515680 KiB

Main

#include <bits/stdc++.h>
#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 std;
//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;

const int tree_siz = 1024*2048-1;
int drzewo[tree_siz+1];

int get_min(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return 1e9;
    if(p1 >= s1 && p2 <= s2) return drzewo[akt];
    return min(get_min(akt*2,p1,(p1+p2)/2,s1,s2),get_min(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}

void upd(int v)
{
    drzewo[v] = min(drzewo[v*2+1],drzewo[v*2]);
    if(v != 1) upd(v/2);
}

void change(int ind, int v)
{
    drzewo[tree_siz/2+1+ind] = v;
    upd((tree_siz/2+ind+1)/2);
}

struct jump_str
{
    int j0,j1,j2;
    int dist = 0;
};

jump_str jump[1000'001][21];

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;
}

int pref[1000'001][3];
vi graph[1000'001];
int comp[1000'001];
int y_index[1000'001];
int cost[1000'001];
vector<pair<pii,int>> seg2;
int real_seg[1000'001];
vector<pii> seg;
bool odw[1000'001];
int m = 1;
int prev_[1000'001][3];
vector<pii> events[1000'001];
int nxt_jump[1000'001];
int down_pref[1000'001];
int best_seg[1000'001];
int r_seg[1000'001];
ll W,H,q;

pii dfs(int v)
{
    comp[v] = m;
    pii w = {y_index[v],y_index[v]};
    forall(it,graph[v])
    {
        if(comp[it] == -1)
        {
            pii w2 = dfs(it);
            w.ff = min(w.ff,w2.ff);
            w.ss = max(w.ss,w2.ss);
        }
    }
    return w;
}

void calc_pointers()
{
    set<int> cost1; 
    set<int> cost2;
    multiset<int> multi;
    vector<pii> eve;
    rep(i,m-1)
    {
        eve.pb({seg[i].ff,i});
        eve.pb({seg[i].ss+1,i+m});
      //  cout << seg[i].ff << " " << i << " add\n";
      //  cout << seg[i].ss+1 << " xd\n";
    }
    sort(all(eve));
    int cur_event = 0;
    rep2(i,1,H)
    {
        while(cur_event != siz(eve) && eve[cur_event].ff == i)
        {
            if(eve[cur_event].ss < m)
            {
                multi.insert(eve[cur_event].ss);
            }
            else
            {
                multi.erase(multi.find(eve[cur_event].ss-m));
            }
            cur_event++;
        }
//        cout << i << " " << siz(multi) << " " << cur_event << " " << eve[cur_event].ff<< " siz\n";
        auto it = multi.end();
        if(it != multi.begin())
        {
            it--;
            best_seg[i] = *it;
        }
        if(cost[i] == 1) cost1.insert(i);
        else cost2.insert(i);
    }
    // rep2(i,1,H)
    // {
    //     cout << best_seg[i] << " " << seg[best_seg[i]].ff << " " << seg[best_seg[i]].ss << " " << i << " best\n";
    // }
    rep(i,m-1)
    {
        //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-1)
    {
        jump[i][0].j2 = max(jump[i][0].j2,jump[jump[i][0].j1][0].j1);
    }
    rep2(bit,1,20)
    {
        rep(i,m)
        {
            jump[i][bit] = merge_jumps(jump[i][bit-1],bit-1);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> H >> W >> q;
    rep(i,tree_siz) drzewo[i+1] = 1e9;
    rep(i,H)
    {
        rep(j,W)
        {
            int cell = i*W+j;
            y_index[cell] = i+1;
            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') 
            {
                down_pref[i+1] = 1;
                graph[cell].pb(cell+W);
                graph[cell+W].pb(cell);
            }
        }
    }
    rep2(i,1,H)
    {
        down_pref[i] += down_pref[i-1];
    }
    rep(i,H) cin >> cost[i+1];
    rep(i,H)
    {
        pref[i+1][1] = pref[i][1];
        pref[i+1][2] = pref[i][2];
        pref[i+1][cost[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));
    rep2(i,1,m-1)
    {
        seg.pb({-seg2[i-1].ff.ss,seg2[i-1].ff.ff});
        real_seg[seg2[i-1].ss] = i-1;
    }
    rep(i,m-1)
    {
        rep2(j,seg[i].ff,seg[i].ss)
        {
            r_seg[j] = i;
        }
    }
    rep(i,H*W) comp[i] = real_seg[comp[i]];
    prev_[0][1] = -1;
    prev_[0][2] = -1;
    rep2(i,1,H)
    {
        prev_[i][1] = prev_[i-1][1];
        prev_[i][2] = prev_[i-1][2];
        if(cost[i] == 1) prev_[i][1] = i;
        if(cost[i] == 2) prev_[i][2] = i;
    }
    multiset<int> mult;
    forall(it,seg)
    {
        events[it.ss].pb({it.ss,1});
        events[it.ff-1].pb({it.ss,-1});
    }
    for(int i = H; i >= 1; i--)
    {
        forall(it,events[i])
        {
            if(it.ss == 1)
            {
                mult.insert(it.ff);
            }
            else
            {
                mult.erase(mult.find(it.ff));
            }
        }
        auto it = mult.end();
        it--;
        nxt_jump[i] = *it;
    }
    calc_pointers();
    rep(qq,q)
    {
        int t;
        cin >> t;
        vector<int> points;
        rep(j,t)
        {
            int y,x;
            cin >> y >> x;
            y--;
            x--;
            int cell = y*W + x;
            points.pb(comp[cell]);
        }
        sort(all(points));
        vi rest;
        int prv = -1;
        int cnt = 0;
        forall(it,points)
        {
            if(it == prv) continue;
            prv = it;
            cnt++;
            if(get_min(1,0,tree_siz/2,seg[it].ff,seg[it].ss) > seg[it].ss) rest.pb(it);
            change(seg[it].ff,seg[it].ss);
        }
        forall(it,points)
        {
            change(seg[it].ff,1e9);
        }
        if(cnt == 1)
        {
            cout << "0\n";
            continue;
        }
      //  cout << siz(rest) << " rest\n";
        if(siz(rest) == 1)
        {
            if(pref[seg[rest[0]].ss][1] - pref[seg[rest[0]].ff-1][1] > 0)
            {
                cout << "1\n";
            }
            else
            {
                cout << "2\n";
            }
            continue;
        }
      //  cout << down_pref[seg[rest[siz(rest)-1]].ss-1] << " " << down_pref[seg[rest[0]].ff-1] << " " << rest[0] << " " << rest[siz(rest)-1] << " " << seg[rest[0]].ff << " " << seg[rest[0]].ss << " " << seg[rest[1]].ff << " " << seg[rest[1]].ss << " down\n"; 
        if(down_pref[seg[rest[siz(rest)-1]].ss-1] - down_pref[seg[rest[0]].ff-1] != seg[rest[siz(rest)-1]].ss-seg[rest[0]].ff)
        {
            cout << "-1\n";
            continue;
        }
        int beg = seg[rest[0]].ff;
        pii dp_ans1;
        pii dp_ans2;
        int cur_ans = 1;
        dp_ans1 = {0,seg[rest[0]].ss};
        int cut = prev_[seg[rest[0]].ss][1];
    //    cout << cut << " cut\n";
        if(cut < beg)
        {
            dp_ans2 = {0,seg[rest[0]].ss};
        }
        else
        {
            int com_l = seg[rest[0]].ff;
            int com_r = seg[rest[0]].ss;
            bool was = 0;
            rep(i,siz(rest))
            {
                int new_l = max(com_l,seg[rest[i]].ff);
                int new_r = min(com_r,seg[rest[i]].ss);
                if(new_l > new_r || cut < new_l || cut > new_r)
                {
                    dp_ans2 = {i-1,nxt_jump[cut]};
                    was = 1;
                    break;
                }
                com_l = new_l;
                com_r = new_r;
            }
            if(!was)
            {
                cout << "1\n";
                continue;
            }
        }
      //  cout << dp_ans1.ff << " " << dp_ans1.ss << " dp\n";
      //  cout << dp_ans2.ff << " " << dp_ans2.ss << " dp2\n";
        while(true)
        {
            if(dp_ans2.ff == siz(rest)-1)
            {
                cout << cur_ans << "\n";
                continue;
            }
         //   cout << cur_ans << " ans\n";
         //   cout << dp_ans1.ff << " " << dp_ans1.ss << " dp\n";
         //   cout << dp_ans2.ff << " " << dp_ans2.ss << " dp2\n\n";      
            cur_ans++;
            if(cur_ans > H*2)
            {
                int a = cur_ans-cur_ans;
                int b = cur_ans;
                cout << b/a;
            } 
            pii new_dp = {-1,-1};
            // ans - 2
            if(prev_[dp_ans1.ss][2] >= beg)
            {
                int v = dp_ans1.ff+1;
                int com_l = seg[rest[v]].ff;
                int com_r = dp_ans1.ss;
                while(com_l <= com_r && v < siz(rest))
                {
                    int new_l = max(com_l,seg[rest[v]].ff);
                    int new_r = min(com_r,seg[rest[v]].ss);
                    if(new_l <= new_r && prev_[new_r][2] >= new_l)
                    {
                        v++;
                        com_l = new_l;
                        com_r = new_r;
                    }
                    else
                    {
                        break;
                    }
                }
             //   cout << v << " v\n";
                new_dp = max(new_dp,{v-1,nxt_jump[prev_[com_r][2]]});
            }
            if(prev_[dp_ans2.ss][1] >= beg)
            {
                int v = dp_ans2.ff+1;
                int com_l = seg[rest[v]].ff;
                int com_r = dp_ans2.ss;
                while(com_l <= com_r && v < siz(rest))
                {
                    int new_l = max(com_l,seg[rest[v]].ff);
                    int new_r = min(com_r,seg[rest[v]].ss);
                    if(new_l <= new_r && prev_[new_r][1] >= new_l)
                    {
                        v++;
                        com_l = new_l;
                        com_r = new_r;
                    }
                    else
                    {
                        break;
                    }
                }
                new_dp = max(new_dp,{v-1,nxt_jump[prev_[com_r][1]]});
            } 
            if(new_dp.ff == siz(rest)-1)
            {
                cout << cur_ans << "\n";
                break;
            }
         //   cout << new_dp.ff << " " << new_dp.ss << " new_dp\n";
            if(new_dp.ff == dp_ans2.ff && dp_ans1.ff == dp_ans2.ff && seg[rest[new_dp.ff+1]].ff > new_dp.ss)
            {
                cur_ans--;
                vector<pair<int,pii>> nxt_dp;
                int v = rest[new_dp.ff+1];
                int v_ind = new_dp.ff+1;
                int end_seg = dp_ans1.ss;
                //dp_ans1
                rep2(k,1,2)
                {
                    if(prev_[end_seg][k] >= beg)
                    {
                        int start_seg = r_seg[prev_[end_seg][k]];
                        jump_str cur_jump = {start_seg,start_seg,start_seg,0};
                        for(int bit = 20; bit >= 0; bit--)
                        {
                            jump_str new_jump = merge_jumps(cur_jump,bit);
                            if(seg[new_jump.j1].ss < seg[v].ff)
                            {
                                cur_jump = new_jump;
                            }
                        }
                        jump_str cur_jump2 = merge_jumps(cur_jump,0);
      //                  cout << jump[3][0].j0 << " " << jump[3][0].j1 << " " << jump[3][0].j2 << " j\n";
      //                  cout << seg[jump[3][0].j1].ff << " " << seg[jump[3][0].j1].ss<< " seg\n"; 
                        if(cur_jump2.j1 == v) 
                        {
                            cur_jump2 = cur_jump;
                        }
              //          cout << cur_jump2.dist << " " << cur_jump2.j1 << " " << seg[cur_jump2.j1].ff << " " << seg[cur_jump2.j1].ss << " jump\n";
              //          cout << cur_ans << " " << k << " " << start_seg << " " << seg[start_seg].ff << " " << seg[start_seg].ss << " ans1\n";
                        nxt_dp.pb({cur_ans-1+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j1].ss}});
                        nxt_dp.pb({cur_ans-2+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j0].ss}});
                    }
                }
                //dp_ans2
                end_seg = dp_ans2.ss;
                rep2(k,1,2)
                {
                    if(prev_[end_seg][k] >= beg)
                    {
                        int start_seg = r_seg[prev_[end_seg][k]];
                        jump_str cur_jump = {start_seg,start_seg,start_seg,0};
                        for(int bit = 20; bit >= 0; bit--)
                        {
                            jump_str new_jump = merge_jumps(cur_jump,bit);
                            if(seg[new_jump.j1].ss < seg[v].ff)
                            {
                                cur_jump = new_jump;
                            }
                        }
                        jump_str cur_jump2 = merge_jumps(cur_jump,0);
                        //                  cout << jump[3][0].j0 << " " << jump[3][0].j1 << " " << jump[3][0].j2 << " j\n";
                        //                  cout << seg[jump[3][0].j1].ff << " " << seg[jump[3][0].j1].ss<< " seg\n"; 
                           //               cout << cur_jump.dist << " " << cur_jump.j1 << " " << seg[cur_jump.j1].ff << " " << seg[cur_jump.j1].ss << " jump\n";
                            //              cout << cur_ans << " " << k << " " << start_seg << " " << seg[start_seg].ff << " " << seg[start_seg].ss << " ans1\n";
                        if(cur_jump2.j1 == v) 
                        {
                            cur_jump2 = cur_jump;
                        }
                        nxt_dp.pb({cur_ans+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j1].ss}});
                        nxt_dp.pb({cur_ans-1+cur_jump2.dist+k,{v_ind-1,seg[cur_jump2.j0].ss}});
                    }
                }
                int mini = 1e9;
                forall(it,nxt_dp)
                {
            //        cout << it.ff << " " << it.ss.ff << " " << it.ss.ss << " nxt\n";
                    mini = min(mini,it.ff);
                }
             //   cout << " nxt_dp\n";
                cur_ans = mini+1;
                dp_ans1 = {-1e9,-1e9};
                dp_ans2 = {-1e9,-1e9};
                forall(it,nxt_dp)
                {
                    if(it.ff == mini)
                    {
                        dp_ans1 = max(dp_ans1,it.ss);
                    }
                    else if(it.ff == mini+1)
                    {
                        dp_ans2 = max(dp_ans2,it.ss);
                    }
                }
            }
            else
            {
                dp_ans1 = dp_ans2;
                dp_ans2 = new_dp;
            }
        }
    }
}

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