oj.uz

Submission #1057011

# Submission time Handle Problem Language Result Execution time Memory
1057011 2024-08-13T13:13:22 Z Alihan_8 Escape Route 2 (JOI24_escape2) C++17
14 / 100
 3000 ms 40976 KB 
#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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 35 ms 9872 KB Output is correct
3 Correct 64 ms 9044 KB Output is correct
4 Correct 109 ms 11492 KB Output is correct
5 Correct 85 ms 9036 KB Output is correct
6 Correct 99 ms 11604 KB Output is correct
7 Correct 98 ms 11572 KB Output is correct
8 Correct 69 ms 9012 KB Output is correct
9 Correct 100 ms 11600 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 35 ms 9872 KB Output is correct
3 Correct 64 ms 9044 KB Output is correct
4 Correct 109 ms 11492 KB Output is correct
5 Correct 85 ms 9036 KB Output is correct
6 Correct 99 ms 11604 KB Output is correct
7 Correct 98 ms 11572 KB Output is correct
8 Correct 69 ms 9012 KB Output is correct
9 Correct 100 ms 11600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 100 ms 10512 KB Output is correct
12 Correct 97 ms 10248 KB Output is correct
13 Correct 88 ms 10432 KB Output is correct
14 Correct 98 ms 10212 KB Output is correct
15 Correct 79 ms 10804 KB Output is correct
16 Correct 55 ms 9860 KB Output is correct
17 Correct 86 ms 11256 KB Output is correct
18 Correct 83 ms 10576 KB Output is correct
19 Correct 88 ms 11088 KB Output is correct
20 Correct 84 ms 10788 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 35 ms 9872 KB Output is correct
3 Correct 64 ms 9044 KB Output is correct
4 Correct 109 ms 11492 KB Output is correct
5 Correct 85 ms 9036 KB Output is correct
6 Correct 99 ms 11604 KB Output is correct
7 Correct 98 ms 11572 KB Output is correct
8 Correct 69 ms 9012 KB Output is correct
9 Correct 100 ms 11600 KB Output is correct
10 Execution timed out 3026 ms 38676 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 35 ms 9872 KB Output is correct
3 Correct 64 ms 9044 KB Output is correct
4 Correct 109 ms 11492 KB Output is correct
5 Correct 85 ms 9036 KB Output is correct
6 Correct 99 ms 11604 KB Output is correct
7 Correct 98 ms 11572 KB Output is correct
8 Correct 69 ms 9012 KB Output is correct
9 Correct 100 ms 11600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 100 ms 10512 KB Output is correct
12 Correct 97 ms 10248 KB Output is correct
13 Correct 88 ms 10432 KB Output is correct
14 Correct 98 ms 10212 KB Output is correct
15 Correct 79 ms 10804 KB Output is correct
16 Correct 55 ms 9860 KB Output is correct
17 Correct 86 ms 11256 KB Output is correct
18 Correct 83 ms 10576 KB Output is correct
19 Correct 88 ms 11088 KB Output is correct
20 Correct 84 ms 10788 KB Output is correct
21 Execution timed out 3026 ms 38676 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1978 ms 25112 KB Output is correct
4 Correct 1952 ms 24976 KB Output is correct
5 Correct 2266 ms 25028 KB Output is correct
6 Correct 2213 ms 25032 KB Output is correct
7 Correct 2178 ms 25048 KB Output is correct
8 Correct 546 ms 25228 KB Output is correct
9 Correct 563 ms 25232 KB Output is correct
10 Correct 50 ms 26768 KB Output is correct
11 Execution timed out 3095 ms 40976 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 35 ms 9872 KB Output is correct
3 Correct 64 ms 9044 KB Output is correct
4 Correct 109 ms 11492 KB Output is correct
5 Correct 85 ms 9036 KB Output is correct
6 Correct 99 ms 11604 KB Output is correct
7 Correct 98 ms 11572 KB Output is correct
8 Correct 69 ms 9012 KB Output is correct
9 Correct 100 ms 11600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 100 ms 10512 KB Output is correct
12 Correct 97 ms 10248 KB Output is correct
13 Correct 88 ms 10432 KB Output is correct
14 Correct 98 ms 10212 KB Output is correct
15 Correct 79 ms 10804 KB Output is correct
16 Correct 55 ms 9860 KB Output is correct
17 Correct 86 ms 11256 KB Output is correct
18 Correct 83 ms 10576 KB Output is correct
19 Correct 88 ms 11088 KB Output is correct
20 Correct 84 ms 10788 KB Output is correct
21 Execution timed out 3026 ms 38676 KB Time limit exceeded
22 Halted 0 ms 0 KB -