Submission #1056891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056891		Alihan_8	Escape Route 2 (JOI24_escape2)	C++17	90 / 100	3047 ms	141096 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 int inf = 1e15;

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;

	void modify(auto a_){
		a = a_, n = a.size();
		m.resize(n); id.resize(n);
		
		int 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(20, -1);
			w[i].resize(20);
		}

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

				//~ for ( int k = 0; k < m[i + 1]; k++ ){
					//~ auto [x, y] = a[i + 1][k];

					//~ ar <int,3> nxt;

					//~ if ( x >= r ){
						//~ nxt = {0, y, k};
					//~ } else{
						//~ nxt = {1, y, k};
					//~ }

					//~ chmin(opt, nxt);
				//~ }

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

		for ( int j = 1; j < 20; 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];
				}
			}
		}
	}

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

        for ( int i = 19; 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;
    }
    
    int qry(int l, int r){
		int 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;
	}
};

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

    int n; cin >> n >> T;

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

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

        a[i].resize(m);

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

	func lf; lf.modify(a);
	
	// reversing a
	for ( int i = 0; i + 1 < n; i++ ){
		int j = n - i - 2, s = a[j].size();
		
		b[i].resize(s);
		
		for ( int k = 0; k < s; k++ ){
			int x = a[j][k][0], y = a[j][k][1];
			
			x = T - x - 1, y = T - y - 1;
			
			b[i][k] = {y, x};
		}
	}
	
	func rg; rg.modify(b);
	
	map <pair<int,int>,int> memo;
	
	auto qry = [&](int l, int r){
		if ( !memo.count({l, r}) ){
			if ( a[l].size() < a[r - 1].size() ){
				memo[{l, r}] = lf.qry(l, r);
			} else{		
				memo[{l, r}] = rg.qry(n - r - 1, n - l - 1);
			}
		}
		
		return memo[{l, r}];
	};

    int q; cin >> q;

    while ( q-- ){
        int l, r; cin >> l >> r;

        --l, --r;
        
        cout << qry(l, r) << ln;
    }

    cout << '\n';
}

Compilation message (stderr)

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

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