Submission #1056862

#TimeUsernameProblemLanguageResultExecution timeMemory
1056862Alihan_8Escape Route 2 (JOI24_escape2)C++17
54 / 100
3062 ms127784 KiB
#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++ ){
			for ( int j = 0; j < m[i]; j++ ){
				auto [l, r] = a[i][j];

				ar <int,3> opt = {inf, -1, -1};

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

    int q; cin >> q;

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

        --l, --r;
        
        if ( a[l].size() < a[r - 1].size() ){
			cout << lf.qry(l, r) << ln;
		} else{		
			cout << rg.qry(n - r - 1, n - l - 1) << 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_){
      |              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...