Submission #1057011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057011		Alihan_8	Escape Route 2 (JOI24_escape2)	C++17	14 / 100	3095 ms	40976 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//~ #define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e15;

const int H = 18;

int T;

struct func{
	// messy struct

	vector <int> m, b;
    vector <vector<ar<int,2>>> a;
	vector <vector<int>> id, up, w;
	vector <ar<int,2>> rev;
    
    int n, ct;

	void modify(auto a_){
		a = a_, n = a.size();
		m.resize(n); id.resize(n);
		ct = 0;

		for ( int i = 0; i + 1 < n; i++ ){
			m[i] = a[i].size();
			id[i].resize(m[i]);

			for ( auto &u: id[i] ) u = ct++;
		}
		
		rev.resize(ct);
		b.resize(ct);

		for ( int i = 0; i + 1 < n; i++ ){
			for ( int j = 0; j < m[i]; j++ ){
				rev[id[i][j]] = a[i][j];
				b[id[i][j]] = i;
			}
		}
		
		up.resize(ct);
		w.resize(ct);
		
		for ( int i = 0; i < ct; i++ ){
			up[i].resize(H, -1);
			w[i].resize(H);
		}

		for ( int i = 0; i + 2 < n; i++ ){
			vector <ar<int,3>> q;
			
			for ( int k = 0; k < m[i + 1]; k++ ){
				auto [x, y] = a[i + 1][k];
				
				q.pb({-x, y, k});
			}
			
			sort(all(q));
			
			set <pair<int,int>> st;
			
			int mn = 2e9;
			
			for ( auto [x, y, k]: q ){
				if ( y >= mn ) continue;
				
				st.insert({-x, k});
				mn = y;
			}
			
			for ( int j = 0; j < m[i]; j++ ){
				auto [l, r] = a[i][j];
	
				ar <int,3> opt;
				
				auto it = st.lower_bound({r, -1});
				
				if ( it != st.end() ){
					opt = {0, a[i + 1][it -> second][1], it -> second};
				} else{
					int k = st.begin() -> second;
					opt = {1, a[i + 1][k][1], k};
				}

				up[id[i][j]][0] = id[i + 1][opt[2]];
				w[id[i][j]][0] = opt[0];
			}
		}

		for ( int j = 1; j < H; j++ ){
			for ( int i = 0; i < ct; i++ ){
				if ( up[i][j - 1] == -1 ){
					up[i][j] = up[i][j - 1];
					w[i][j] = w[i][j - 1];
				} else{
					up[i][j] = up[up[i][j - 1]][j - 1];
					w[i][j] = w[i][j - 1] + w[up[i][j - 1]][j - 1];
				}
			}
		}
	}

    i64 get(int u, int r){
        i64 cnt = 0;

        for ( int i = H - 1; i >= 0; i-- ){
            if ( up[u][i] == -1 ){
                continue;
            }

            if ( b[up[u][i]] < r ){
                cnt += w[u][i];

                u = up[u][i];
            }
        }

        cnt = cnt * T + rev[u][1];

        return cnt;
    }
    
    i64 qry(int l, int r){
		i64 opt = inf;

        for ( int j = 0; j < m[l]; j++ ){
            auto [x, y] = a[l][j];

            chmin(opt, get(id[l][j], r) - x);
        }
        
        return opt;
	}
	
	auto RunDjk(int sx){
		vector <i64> dp(ct, inf);
		
		priority_queue <ar<i64,2>> q;
		
		for ( int i = 0; i < m[sx]; i++ ){
			dp[id[sx][i]] = a[sx][i][1] - a[sx][i][0];
			q.push({-dp[id[sx][i]], id[sx][i]});
		}
		
		while ( !q.empty() ){
			auto [val, u] = q.top();
			q.pop();
			
			if ( -val != dp[u] ) continue;
			
			if ( up[u][0] != -1 ){
				int nxt = up[u][0];
				
				i64 cost = -val + (w[u][0] ? T - rev[u][1] + rev[nxt][1] : rev[nxt][1] - rev[u][1]);
				
				if ( chmin(dp[nxt], cost) ){
					q.push({-cost, nxt});
				}
			}
		}
		
		vector <i64> f(n, inf);
		
		for ( int i = 0; i < ct; i++ ){
			chmin(f[b[i] + 1], dp[i]);
		}
		
		return f;
	}
};

const int B = 1000;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n >> T;

    vector <vector<ar<int,2>>> a(n);
    
    vector <int> m(n);

    for ( int i = 0; i + 1 < n; i++ ){
        cin >> m[i];

        a[i].resize(m[i]);

        for ( auto &[l, r]: a[i] ){
            cin >> l >> r;
        }
    }

	func lf; lf.modify(a);

    int q; cin >> q;
    
    vector <vector<ar<int,2>>> qu(n);

	for ( int i = 0; i < q; i++ ){
		int l, r; cin >> l >> r;
		
		--l, --r;
		
		qu[l].pb({i, r});
	}
	
	vector <i64> ans(q, inf);
	
	for ( int i = 0; i + 1 < n; i++ ){
		if ( m[i] < B ){
			for ( auto &[j, r]: qu[i] ){
				ans[j] = lf.qry(i, r);
			}
		}
		
		auto bst = lf.RunDjk(i);
		
		for ( auto &[j, r]: qu[i] ){
			ans[j] = bst[r];
		}
	}
	
	for ( auto &x: ans ){
		cout << x << ln;
	}

    cout << '\n';
}

Compilation message (stderr)

Main.cpp:47:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   47 |  void modify(auto a_){
      |              ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 17
• Subtask 4: 0 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10