oj.uz

Submission #718904

# Submission time Handle Problem Language Result Execution time Memory
718904 2023-04-05T06:19:32 Z vinnipuh01 Railway Trip 2 (JOI22_ho_t4) C++17
87 / 100
 2000 ms 79360 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define sqrt sqrtl
 
using namespace std;
 
const long long oo = 1e9;
 
int sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
 
 
/*
    ViHHiPuh
 
   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
 
 
    cout << fixed << setprecision(6) << x;
 
 
    freopen ( "sum.in", "r", stdin )
*/
 
int n, m, q, k, a[ 200001 ], b[ 200001 ], s[ 50001 ], f[ 50001 ];
 
struct Node {
	int mx, mn;
	
	void clear(  ) {
		mx = 0;
		mn = n + 1;
	}
	
} t[ 20 ][ 400001 ], p[ 20 ][ 400001 ], an;
 
vector <int> v[ 2001 ];
 
void build( int v, int tl, int tr ) {
	p[ pos ][ v ].mn = n + 1;
	if ( tl == tr ) {
		t[ pos ][ v ].mx = tl;
		t[ pos ][ v ].mn = tl;
		return;
	}
	int mid = ( tl + tr ) / 2;
	build( v + v, tl, mid );
	build( v + v + 1, mid + 1, tr );
	t[ pos ][ v ].mx = max( t[ pos ][ v + v ].mx, t[ pos ][ v + v + 1 ].mx );
	t[ pos ][ v ].mn = min( t[ pos ][ v + v ].mn, t[ pos ][ v + v + 1 ].mn );
}
 
void pus( int v ) {
	if ( p[ pos ][ v ].mx ) {
		p[ pos ][ v + v ].mx = max( p[ pos ][ v + v ].mx, p[ pos ][ v ].mx );
		p[ pos ][ v + v + 1 ].mx = max( p[ pos ][ v + v + 1 ].mx, p[ pos ][ v ].mx );
		t[ pos ][ v + v ].mx = max( t[ pos ][ v + v ].mx, p[ pos ][ v ].mx );
		t[ pos ][ v + v + 1 ].mx = max( t[ pos ][ v + v + 1 ].mx, p[ pos ][ v ].mx );
		p[ pos ][ v ].mx = 0;
	}
	if ( p[ pos ][ v ].mn != n + 1 ) {
		p[ pos ][ v + v ].mn = min( p[ pos ][ v + v ].mn, p[ pos ][ v ].mn );
		p[ pos ][ v + v + 1 ].mn= min( p[ pos ][ v + v + 1 ].mn, p[ pos ][ v ].mn );
		t[ pos ][ v + v ].mn = min( t[ pos ][ v + v ].mn, p[ pos ][ v ].mn );
		t[ pos ][ v + v + 1 ].mn = min( t[ pos ][ v + v + 1 ].mn, p[ pos ][ v ].mn );
		p[ pos ][ v ].mn = n + 1;
	}
}
 
void upd( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
//		cout << tl << " " << tr << " x- " << num << "\n";
		t[ pos ][ v ].mx = max( t[ pos ][ v ].mx, num );
		p[ pos ][ v ].mx = max( p[ pos ][ v ].mx, num );
		return;
	}
	pus( v );
	int mid = ( tl + tr ) / 2;
	upd( v + v, tl, mid, l, r );
	upd( v + v + 1, mid + 1, tr, l, r );
	t[ pos ][ v ].mx = max( t[ pos ][ v + v ].mx, t[ pos ][ v + v + 1 ].mx ); 
}
 
void updd( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
//		cout << tl << " " << tr << " n- " << num << "\n";
		t[ pos ][ v ].mn = min( t[ pos ][ v ].mn, num );
		p[ pos ][ v ].mn = min( p[ pos ][ v ].mn, num );
		return;
	}
	pus( v );
	int mid = ( tl + tr ) / 2;
	updd( v + v, tl, mid, l, r );
	updd( v + v + 1, mid + 1, tr, l, r );
	t[ pos ][ v ].mn = min( t[ pos ][ v + v ].mn, t[ pos ][ v + v + 1 ].mn );
}
 
void gett( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		an.mx = max( an.mx, t[ pos ][ v ].mx );
		an.mn = min( an.mn, t[ pos ][ v ].mn );
		return;
	}
	pus( v );
	int mid = ( tl + tr ) / 2;
	gett( v + v, tl, mid, l, r );
	gett( v + v + 1, mid + 1, tr, l, r );
}
 
void lca( int l, int r, int b ) {
	ans = 0;
	num = 0;
	for ( int i = 17; i >= 0; i -- ) {
		an.clear();
		pos = i;
		gett( 1, 1, n, l, r );
		if ( an.mx < b || an.mn > b ) {
			l = min( an.mn, l );
			r = max( an.mx, r );
//			cout << i << ", ";
			ans += ( 1ll << i );
		}
	}
	ans ++;
	return;
}
 
main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n >> k;
	cin >> m;
	for ( int i = 1; i <= m; i ++ ) {
		cin >> a[ i ] >> b[ i ];
	}
	cin >> q;
	for ( int i = 0; i < 18; i ++ )
		pos = i, build( 1, 1, n );
	for ( int i = 1; i <= q; i ++ ) {
		cin >> s[ i ] >> f[ i ];
	}
//	if ( n <= 2000 && m <= 2000 && q <= 2000 ) {
//		
//	}
	for ( int i = 1; i <= m; i ++ ) {
		if ( a[ i ] > b[ i ] ) {
			num = b[ i ];
			pos = 0;
			updd( 1, 1, n, a[ i ] - k + 1, a[ i ] );
		}
		else {
			num = b[ i ];
			pos = 0;
			upd( 1, 1, n, a[ i ], a[ i ] + k - 1 );
		}
	}
	int l = n + 1, r = 0;
	for ( int i = 1; i < 18; i ++ ) {
		for ( int j = 1; j <= n; j ++ ) {
			an.clear();
			pos = i - 1;
			gett( 1, 1, n, j, j );
			l = an.mn;
			r = an.mx;
			if ( !r )
				r = j;
			if ( l == n + 1 )
				l = j;
			an.clear();
			gett( 1, 1, n, l, r );
			num = an.mx;
			pos = i;
			upd( 1, 1, n, j, j );
			num = an.mn;
			updd( 1, 1, n, j, j );
		}
	}
//	for ( int i = 0; i < 20; i ++ ) {
//		for ( int j = 1; j <= n; j ++ ) {
//			pos = i;
//			an.clear();
//			gett( 1, 1, n, j, j );
//			cout << j << " " << i << " - " << an.mn << " " << an.mx << endl;
//		}
//	}
	for ( int i = 1; i <= q; i ++ ) {
		if ( s[ i ] == f[ i ] ) {
			cout << "0\n";
			continue;
		}
		lca( s[ i ], s[ i ], f[ i ] );
		if ( ans == ( 1 << 18 ) )
			cout << "-1\n";
		else
			cout << ans << "\n";
	}
}

Compilation message

Main.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  153 | main () {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 28 ms 1856 KB Output is correct
14 Correct 28 ms 1748 KB Output is correct
15 Correct 24 ms 1844 KB Output is correct
16 Correct 23 ms 1748 KB Output is correct
17 Correct 26 ms 1856 KB Output is correct
18 Correct 23 ms 1860 KB Output is correct
19 Correct 27 ms 1748 KB Output is correct
20 Correct 21 ms 1864 KB Output is correct
21 Correct 16 ms 1848 KB Output is correct
22 Correct 23 ms 1860 KB Output is correct
23 Correct 25 ms 1748 KB Output is correct
24 Correct 26 ms 1860 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 75212 KB Output is correct
2 Correct 1463 ms 75088 KB Output is correct
3 Correct 1629 ms 75340 KB Output is correct
4 Correct 1494 ms 75040 KB Output is correct
5 Correct 1280 ms 76016 KB Output is correct
6 Correct 1529 ms 76016 KB Output is correct
7 Correct 1162 ms 76016 KB Output is correct
8 Correct 1090 ms 75244 KB Output is correct
9 Correct 1119 ms 75300 KB Output is correct
10 Correct 1586 ms 76020 KB Output is correct
11 Correct 1440 ms 76020 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1632 ms 75588 KB Output is correct
2 Correct 1541 ms 76528 KB Output is correct
3 Correct 1866 ms 75880 KB Output is correct
4 Correct 1417 ms 79116 KB Output is correct
5 Correct 1315 ms 79196 KB Output is correct
6 Correct 1319 ms 79168 KB Output is correct
7 Correct 1823 ms 79316 KB Output is correct
8 Correct 1677 ms 79328 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 76532 KB Output is correct
2 Correct 1933 ms 75972 KB Output is correct
3 Correct 1868 ms 76520 KB Output is correct
4 Correct 1874 ms 76120 KB Output is correct
5 Correct 1727 ms 75724 KB Output is correct
6 Correct 1752 ms 75488 KB Output is correct
7 Correct 1542 ms 77576 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 23 ms 1892 KB Output is correct
10 Correct 1474 ms 78412 KB Output is correct
11 Correct 1642 ms 79176 KB Output is correct
12 Correct 1576 ms 79192 KB Output is correct
13 Correct 1607 ms 79180 KB Output is correct
14 Correct 4 ms 852 KB Output is correct
15 Correct 25 ms 1872 KB Output is correct
16 Correct 1471 ms 78332 KB Output is correct
17 Correct 1923 ms 79360 KB Output is correct
18 Correct 1854 ms 79332 KB Output is correct
19 Correct 1747 ms 79316 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 28 ms 1856 KB Output is correct
14 Correct 28 ms 1748 KB Output is correct
15 Correct 24 ms 1844 KB Output is correct
16 Correct 23 ms 1748 KB Output is correct
17 Correct 26 ms 1856 KB Output is correct
18 Correct 23 ms 1860 KB Output is correct
19 Correct 27 ms 1748 KB Output is correct
20 Correct 21 ms 1864 KB Output is correct
21 Correct 16 ms 1848 KB Output is correct
22 Correct 23 ms 1860 KB Output is correct
23 Correct 25 ms 1748 KB Output is correct
24 Correct 26 ms 1860 KB Output is correct
25 Correct 1483 ms 75212 KB Output is correct
26 Correct 1463 ms 75088 KB Output is correct
27 Correct 1629 ms 75340 KB Output is correct
28 Correct 1494 ms 75040 KB Output is correct
29 Correct 1280 ms 76016 KB Output is correct
30 Correct 1529 ms 76016 KB Output is correct
31 Correct 1162 ms 76016 KB Output is correct
32 Correct 1090 ms 75244 KB Output is correct
33 Correct 1119 ms 75300 KB Output is correct
34 Correct 1586 ms 76020 KB Output is correct
35 Correct 1440 ms 76020 KB Output is correct
36 Correct 1632 ms 75588 KB Output is correct
37 Correct 1541 ms 76528 KB Output is correct
38 Correct 1866 ms 75880 KB Output is correct
39 Correct 1417 ms 79116 KB Output is correct
40 Correct 1315 ms 79196 KB Output is correct
41 Correct 1319 ms 79168 KB Output is correct
42 Correct 1823 ms 79316 KB Output is correct
43 Correct 1677 ms 79328 KB Output is correct
44 Correct 1702 ms 76532 KB Output is correct
45 Correct 1933 ms 75972 KB Output is correct
46 Correct 1868 ms 76520 KB Output is correct
47 Correct 1874 ms 76120 KB Output is correct
48 Correct 1727 ms 75724 KB Output is correct
49 Correct 1752 ms 75488 KB Output is correct
50 Correct 1542 ms 77576 KB Output is correct
51 Correct 3 ms 852 KB Output is correct
52 Correct 23 ms 1892 KB Output is correct
53 Correct 1474 ms 78412 KB Output is correct
54 Correct 1642 ms 79176 KB Output is correct
55 Correct 1576 ms 79192 KB Output is correct
56 Correct 1607 ms 79180 KB Output is correct
57 Correct 4 ms 852 KB Output is correct
58 Correct 25 ms 1872 KB Output is correct
59 Correct 1471 ms 78332 KB Output is correct
60 Correct 1923 ms 79360 KB Output is correct
61 Correct 1854 ms 79332 KB Output is correct
62 Correct 1747 ms 79316 KB Output is correct
63 Correct 1847 ms 76992 KB Output is correct
64 Execution timed out 2036 ms 77536 KB Time limit exceeded
65 Halted 0 ms 0 KB -