oj.uz

Submission #1056901

# Submission time Handle Problem Language Result Execution time Memory
1056901 2024-08-13T12:15:17 Z Alihan_8 Escape Route 2 (JOI24_escape2) C++17
90 / 100
 3000 ms 100412 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;

	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(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;
	}
};

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>,i64> 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

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 348 KB Output is correct
2 Correct 29 ms 3268 KB Output is correct
3 Correct 190 ms 17744 KB Output is correct
4 Correct 245 ms 23632 KB Output is correct
5 Correct 203 ms 18808 KB Output is correct
6 Correct 301 ms 23176 KB Output is correct
7 Correct 289 ms 23268 KB Output is correct
8 Correct 215 ms 17348 KB Output is correct
9 Correct 276 ms 23332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 29 ms 3268 KB Output is correct
3 Correct 190 ms 17744 KB Output is correct
4 Correct 245 ms 23632 KB Output is correct
5 Correct 203 ms 18808 KB Output is correct
6 Correct 301 ms 23176 KB Output is correct
7 Correct 289 ms 23268 KB Output is correct
8 Correct 215 ms 17348 KB Output is correct
9 Correct 276 ms 23332 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 168 ms 9844 KB Output is correct
12 Correct 158 ms 9908 KB Output is correct
13 Correct 160 ms 9852 KB Output is correct
14 Correct 175 ms 9760 KB Output is correct
15 Correct 216 ms 16544 KB Output is correct
16 Correct 32 ms 3444 KB Output is correct
17 Correct 286 ms 22024 KB Output is correct
18 Correct 242 ms 17236 KB Output is correct
19 Correct 294 ms 21436 KB Output is correct
20 Correct 227 ms 15748 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 29 ms 3268 KB Output is correct
3 Correct 190 ms 17744 KB Output is correct
4 Correct 245 ms 23632 KB Output is correct
5 Correct 203 ms 18808 KB Output is correct
6 Correct 301 ms 23176 KB Output is correct
7 Correct 289 ms 23268 KB Output is correct
8 Correct 215 ms 17348 KB Output is correct
9 Correct 276 ms 23332 KB Output is correct
10 Correct 474 ms 75540 KB Output is correct
11 Correct 781 ms 98984 KB Output is correct
12 Correct 682 ms 98996 KB Output is correct
13 Correct 602 ms 94536 KB Output is correct
14 Correct 825 ms 100412 KB Output is correct
15 Correct 681 ms 100364 KB Output is correct
16 Correct 433 ms 76816 KB Output is correct
17 Correct 661 ms 100396 KB Output is correct
18 Correct 220 ms 76268 KB Output is correct
19 Correct 181 ms 75536 KB Output is correct
20 Correct 201 ms 76468 KB Output is correct
21 Correct 219 ms 76592 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 29 ms 3268 KB Output is correct
3 Correct 190 ms 17744 KB Output is correct
4 Correct 245 ms 23632 KB Output is correct
5 Correct 203 ms 18808 KB Output is correct
6 Correct 301 ms 23176 KB Output is correct
7 Correct 289 ms 23268 KB Output is correct
8 Correct 215 ms 17348 KB Output is correct
9 Correct 276 ms 23332 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 168 ms 9844 KB Output is correct
12 Correct 158 ms 9908 KB Output is correct
13 Correct 160 ms 9852 KB Output is correct
14 Correct 175 ms 9760 KB Output is correct
15 Correct 216 ms 16544 KB Output is correct
16 Correct 32 ms 3444 KB Output is correct
17 Correct 286 ms 22024 KB Output is correct
18 Correct 242 ms 17236 KB Output is correct
19 Correct 294 ms 21436 KB Output is correct
20 Correct 227 ms 15748 KB Output is correct
21 Correct 474 ms 75540 KB Output is correct
22 Correct 781 ms 98984 KB Output is correct
23 Correct 682 ms 98996 KB Output is correct
24 Correct 602 ms 94536 KB Output is correct
25 Correct 825 ms 100412 KB Output is correct
26 Correct 681 ms 100364 KB Output is correct
27 Correct 433 ms 76816 KB Output is correct
28 Correct 661 ms 100396 KB Output is correct
29 Correct 220 ms 76268 KB Output is correct
30 Correct 181 ms 75536 KB Output is correct
31 Correct 201 ms 76468 KB Output is correct
32 Correct 219 ms 76592 KB Output is correct
33 Correct 668 ms 74328 KB Output is correct
34 Correct 637 ms 74156 KB Output is correct
35 Correct 701 ms 69752 KB Output is correct
36 Correct 720 ms 69752 KB Output is correct
37 Correct 566 ms 73364 KB Output is correct
38 Correct 477 ms 67972 KB Output is correct
39 Correct 561 ms 84536 KB Output is correct
40 Correct 494 ms 56132 KB Output is correct
41 Correct 526 ms 68804 KB Output is correct
42 Correct 689 ms 88904 KB Output is correct
43 Correct 535 ms 73792 KB Output is correct
44 Correct 621 ms 78464 KB Output is correct
45 Correct 235 ms 65996 KB Output is correct
46 Correct 214 ms 56464 KB Output is correct

Subtask #5
36.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 855 ms 46268 KB Output is correct
4 Correct 836 ms 46392 KB Output is correct
5 Correct 956 ms 46420 KB Output is correct
6 Correct 1331 ms 46160 KB Output is correct
7 Correct 1294 ms 46228 KB Output is correct
8 Correct 397 ms 46420 KB Output is correct
9 Correct 257 ms 46672 KB Output is correct
10 Correct 57 ms 43920 KB Output is correct
11 Correct 209 ms 76052 KB Output is correct
12 Correct 244 ms 66224 KB Output is correct
13 Correct 254 ms 56592 KB Output is correct
14 Correct 150 ms 52288 KB Output is correct
15 Correct 140 ms 51364 KB Output is correct
16 Correct 162 ms 54416 KB Output is correct
17 Correct 180 ms 53652 KB Output is correct
18 Correct 158 ms 47212 KB Output is correct
19 Correct 224 ms 45892 KB Output is correct
20 Correct 164 ms 67156 KB Output is correct
21 Correct 215 ms 67048 KB Output is correct
22 Correct 233 ms 55428 KB Output is correct
23 Correct 285 ms 56068 KB Output is correct
24 Correct 148 ms 56596 KB Output is correct
25 Correct 108 ms 56388 KB Output is correct
26 Correct 188 ms 58108 KB Output is correct
27 Correct 207 ms 75508 KB Output is correct
28 Correct 228 ms 76308 KB Output is correct
29 Correct 215 ms 76272 KB Output is correct
30 Correct 179 ms 50712 KB Output is correct
31 Correct 81 ms 44576 KB Output is correct
32 Correct 244 ms 49748 KB Output is correct
33 Correct 101 ms 45064 KB Output is correct
34 Correct 318 ms 47476 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 29 ms 3268 KB Output is correct
3 Correct 190 ms 17744 KB Output is correct
4 Correct 245 ms 23632 KB Output is correct
5 Correct 203 ms 18808 KB Output is correct
6 Correct 301 ms 23176 KB Output is correct
7 Correct 289 ms 23268 KB Output is correct
8 Correct 215 ms 17348 KB Output is correct
9 Correct 276 ms 23332 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 168 ms 9844 KB Output is correct
12 Correct 158 ms 9908 KB Output is correct
13 Correct 160 ms 9852 KB Output is correct
14 Correct 175 ms 9760 KB Output is correct
15 Correct 216 ms 16544 KB Output is correct
16 Correct 32 ms 3444 KB Output is correct
17 Correct 286 ms 22024 KB Output is correct
18 Correct 242 ms 17236 KB Output is correct
19 Correct 294 ms 21436 KB Output is correct
20 Correct 227 ms 15748 KB Output is correct
21 Correct 474 ms 75540 KB Output is correct
22 Correct 781 ms 98984 KB Output is correct
23 Correct 682 ms 98996 KB Output is correct
24 Correct 602 ms 94536 KB Output is correct
25 Correct 825 ms 100412 KB Output is correct
26 Correct 681 ms 100364 KB Output is correct
27 Correct 433 ms 76816 KB Output is correct
28 Correct 661 ms 100396 KB Output is correct
29 Correct 220 ms 76268 KB Output is correct
30 Correct 181 ms 75536 KB Output is correct
31 Correct 201 ms 76468 KB Output is correct
32 Correct 219 ms 76592 KB Output is correct
33 Correct 668 ms 74328 KB Output is correct
34 Correct 637 ms 74156 KB Output is correct
35 Correct 701 ms 69752 KB Output is correct
36 Correct 720 ms 69752 KB Output is correct
37 Correct 566 ms 73364 KB Output is correct
38 Correct 477 ms 67972 KB Output is correct
39 Correct 561 ms 84536 KB Output is correct
40 Correct 494 ms 56132 KB Output is correct
41 Correct 526 ms 68804 KB Output is correct
42 Correct 689 ms 88904 KB Output is correct
43 Correct 535 ms 73792 KB Output is correct
44 Correct 621 ms 78464 KB Output is correct
45 Correct 235 ms 65996 KB Output is correct
46 Correct 214 ms 56464 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 855 ms 46268 KB Output is correct
50 Correct 836 ms 46392 KB Output is correct
51 Correct 956 ms 46420 KB Output is correct
52 Correct 1331 ms 46160 KB Output is correct
53 Correct 1294 ms 46228 KB Output is correct
54 Correct 397 ms 46420 KB Output is correct
55 Correct 257 ms 46672 KB Output is correct
56 Correct 57 ms 43920 KB Output is correct
57 Correct 209 ms 76052 KB Output is correct
58 Correct 244 ms 66224 KB Output is correct
59 Correct 254 ms 56592 KB Output is correct
60 Correct 150 ms 52288 KB Output is correct
61 Correct 140 ms 51364 KB Output is correct
62 Correct 162 ms 54416 KB Output is correct
63 Correct 180 ms 53652 KB Output is correct
64 Correct 158 ms 47212 KB Output is correct
65 Correct 224 ms 45892 KB Output is correct
66 Correct 164 ms 67156 KB Output is correct
67 Correct 215 ms 67048 KB Output is correct
68 Correct 233 ms 55428 KB Output is correct
69 Correct 285 ms 56068 KB Output is correct
70 Correct 148 ms 56596 KB Output is correct
71 Correct 108 ms 56388 KB Output is correct
72 Correct 188 ms 58108 KB Output is correct
73 Correct 207 ms 75508 KB Output is correct
74 Correct 228 ms 76308 KB Output is correct
75 Correct 215 ms 76272 KB Output is correct
76 Correct 179 ms 50712 KB Output is correct
77 Correct 81 ms 44576 KB Output is correct
78 Correct 244 ms 49748 KB Output is correct
79 Correct 101 ms 45064 KB Output is correct
80 Correct 318 ms 47476 KB Output is correct
81 Correct 2201 ms 60328 KB Output is correct
82 Correct 2123 ms 63632 KB Output is correct
83 Correct 2120 ms 63568 KB Output is correct
84 Execution timed out 3066 ms 63112 KB Time limit exceeded
85 Halted 0 ms 0 KB -