oj.uz

Submission #1057007

# Submission time Handle Problem Language Result Execution time Memory
1057007 2024-08-13T13:10:46 Z Alihan_8 Escape Route 2 (JOI24_escape2) C++17
14 / 100
 3000 ms 42760 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 = 500;

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 1 ms 344 KB Output is correct
2 Correct 35 ms 8896 KB Output is correct
3 Correct 84 ms 10240 KB Output is correct
4 Correct 113 ms 12884 KB Output is correct
5 Correct 98 ms 10332 KB Output is correct
6 Correct 103 ms 13236 KB Output is correct
7 Correct 100 ms 13120 KB Output is correct
8 Correct 65 ms 10320 KB Output is correct
9 Correct 99 ms 13108 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 35 ms 8896 KB Output is correct
3 Correct 84 ms 10240 KB Output is correct
4 Correct 113 ms 12884 KB Output is correct
5 Correct 98 ms 10332 KB Output is correct
6 Correct 103 ms 13236 KB Output is correct
7 Correct 100 ms 13120 KB Output is correct
8 Correct 65 ms 10320 KB Output is correct
9 Correct 99 ms 13108 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 96 ms 11804 KB Output is correct
12 Correct 95 ms 11600 KB Output is correct
13 Correct 88 ms 11604 KB Output is correct
14 Correct 88 ms 11552 KB Output is correct
15 Correct 78 ms 11976 KB Output is correct
16 Correct 50 ms 9920 KB Output is correct
17 Correct 85 ms 12624 KB Output is correct
18 Correct 82 ms 11856 KB Output is correct
19 Correct 90 ms 12708 KB Output is correct
20 Correct 88 ms 12112 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 35 ms 8896 KB Output is correct
3 Correct 84 ms 10240 KB Output is correct
4 Correct 113 ms 12884 KB Output is correct
5 Correct 98 ms 10332 KB Output is correct
6 Correct 103 ms 13236 KB Output is correct
7 Correct 100 ms 13120 KB Output is correct
8 Correct 65 ms 10320 KB Output is correct
9 Correct 99 ms 13108 KB Output is correct
10 Execution timed out 3043 ms 41068 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 35 ms 8896 KB Output is correct
3 Correct 84 ms 10240 KB Output is correct
4 Correct 113 ms 12884 KB Output is correct
5 Correct 98 ms 10332 KB Output is correct
6 Correct 103 ms 13236 KB Output is correct
7 Correct 100 ms 13120 KB Output is correct
8 Correct 65 ms 10320 KB Output is correct
9 Correct 99 ms 13108 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 96 ms 11804 KB Output is correct
12 Correct 95 ms 11600 KB Output is correct
13 Correct 88 ms 11604 KB Output is correct
14 Correct 88 ms 11552 KB Output is correct
15 Correct 78 ms 11976 KB Output is correct
16 Correct 50 ms 9920 KB Output is correct
17 Correct 85 ms 12624 KB Output is correct
18 Correct 82 ms 11856 KB Output is correct
19 Correct 90 ms 12708 KB Output is correct
20 Correct 88 ms 12112 KB Output is correct
21 Execution timed out 3043 ms 41068 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1916 ms 26584 KB Output is correct
4 Correct 1940 ms 26512 KB Output is correct
5 Correct 2171 ms 26516 KB Output is correct
6 Correct 2159 ms 26576 KB Output is correct
7 Correct 2239 ms 26644 KB Output is correct
8 Correct 606 ms 26764 KB Output is correct
9 Correct 92 ms 26772 KB Output is correct
10 Correct 65 ms 28048 KB Output is correct
11 Execution timed out 3064 ms 42760 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 35 ms 8896 KB Output is correct
3 Correct 84 ms 10240 KB Output is correct
4 Correct 113 ms 12884 KB Output is correct
5 Correct 98 ms 10332 KB Output is correct
6 Correct 103 ms 13236 KB Output is correct
7 Correct 100 ms 13120 KB Output is correct
8 Correct 65 ms 10320 KB Output is correct
9 Correct 99 ms 13108 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 96 ms 11804 KB Output is correct
12 Correct 95 ms 11600 KB Output is correct
13 Correct 88 ms 11604 KB Output is correct
14 Correct 88 ms 11552 KB Output is correct
15 Correct 78 ms 11976 KB Output is correct
16 Correct 50 ms 9920 KB Output is correct
17 Correct 85 ms 12624 KB Output is correct
18 Correct 82 ms 11856 KB Output is correct
19 Correct 90 ms 12708 KB Output is correct
20 Correct 88 ms 12112 KB Output is correct
21 Execution timed out 3043 ms 41068 KB Time limit exceeded
22 Halted 0 ms 0 KB -