Submission #49275012

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int n, m, Q;
struct Segment {
	int l, r, dat, tag;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat(x) tree[x].dat
	#define tag(x) tree[x].tag
}tree[maxn << 4];
vector < int > xs;
int f[maxn << 2][25];
struct node {
	int x_i, y_i, z_i, w_i;
}a[maxn];
struct qu {
	int L_i, R_i;
};
vector < qu > loc[maxn];
vector < qu > New[maxn];

bool cmp(qu a, qu b) {
	return (a.L_i < b.L_i || (a.L_i == b.L_i && a.R_i < b.R_i));
}

int Find(int x) {
	return lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
}

void build(int p, int l, int r) {
	l(p) = l, r(p) = r, dat(p) = 0;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
}

inline void update(int p) {
	dat(p) = max(dat(p << 1), dat(p << 1 | 1));
}

inline void spread(int p) {
	if(tag(p)) {
		tag(p << 1) = max(tag(p << 1), tag(p)), tag(p << 1 | 1) = max(tag(p << 1 | 1), tag(p));
		dat(p << 1) = max(dat(p << 1), tag(p)), dat(p << 1 | 1) = max(dat(p << 1 | 1), tag(p));
		tag(p) = 0;
	}
}

void modify(int p, int l, int r) {
	if(l <= l(p) && r(p) <= r) return dat(p) = max(dat(p), r), tag(p) = max(tag(p), r), void();
	spread(p);
	int mid = l(p) + r(p) >> 1;
	if(l <= mid) modify(p << 1, l, r);
	if(r > mid) modify(p << 1 | 1, l, r);
	update(p);
}

int query(int p, int x) {
	if(l(p) == r(p)) return dat(p);
	spread(p);
	int mid = l(p) + r(p) >> 1;
	if(x <= mid) return query(p << 1, x);
	else return query(p << 1 | 1, x);
}

int jmp(int x, int y) {
	int res = 1;
	for(int i = 24; i >= 0; i --) {
		if(f[x][i] < y) res += (1 << i), x = f[x][i];
	}
	x = f[x][0], res ++;
	if(x < y) return -1;
	return res;
}

inline int rev(int x) {
	return xs[x - 1];
}

void solve(int x, int pos) {
	if(pos == loc[x].size()) return ;
	int L = loc[x][pos].L_i, R = loc[x][pos].R_i;
	while(pos < loc[x].size() - 1 && loc[x][pos + 1].L_i <= R) R = max(R, loc[x][pos + 1].R_i), pos ++;
	xs.push_back(L), xs.push_back(R);
	New[x].push_back({L, R});
	solve(x, pos + 1);
}

int main() {
//	freopen("data.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &Q);
	for(int i = 1, a, b, c; i <= m; i ++) scanf("%d%d%d", &a, &b, &c), loc[a].push_back({b, c});
	for(int i = 1; i <= n; i ++) {
//		printf("i:%d\n", i);
		sort(loc[i].begin(), loc[i].end(), cmp);
//		for(int j = 0; j < loc[i].size(); j ++) printf("-- %d %d\n", loc[i][j].L_i, loc[i][j].R_i);
		solve(i, 0);
	}
//	for(int i = 1; i <= n; i ++) {
//		printf("i:%d\n", i);
//		for(int j = 0; j < New[i].size(); j ++) printf("---- %d %d\n", New[i][j].L_i, New[i][j].R_i);
//	}
	for(int i = 1; i <= Q; i ++) {
		scanf("%d%d%d%d", &a[i].x_i, &a[i].y_i, &a[i].z_i, &a[i].w_i);
		if(a[i].y_i > a[i].w_i) swap(a[i].x_i, a[i].z_i), swap(a[i].y_i, a[i].w_i);
		xs.push_back(a[i].y_i), xs.push_back(a[i].w_i);
	}
	sort(xs.begin(), xs.end()), xs.erase(unique(xs.begin(), xs.end()), xs.end());
//	puts("-----"); for(auto i : xs) printf("%d ", i); puts("");
	for(int i = 1; i <= Q; i ++) a[i].y_i = Find(a[i].y_i), a[i].w_i = Find(a[i].w_i);
	int N = xs.size();
	build(1, 1, N);
	for(int i = 1; i <= n; i ++) {
//		printf("i:%d\n", i);
		for(int j = 0; j < New[i].size(); j ++) New[i][j].L_i = Find(New[i][j].L_i), New[i][j].R_i = Find(New[i][j].R_i), modify(1, New[i][j].L_i, New[i][j].R_i);// printf("l:%d r:%d\n", New[i][j].L_i, New[i][j].R_i);
	}
	for(int i = 1; i <= N; i ++) f[i][0] = query(1, i);
	for(int i = 1; i < 25; i ++)
		for(int j = 1; j <= N; j ++)
			f[j][i] = f[f[j][i - 1]][i - 1];
//	for(int j = 1; j <= N; j ++)
//		for(int i = 0; i < 4; i ++)
//			printf("f[%d][%d]:%d\n", j, i, f[j][i]);
	for(int i = 1, x, y, z, w; i <= Q; i ++) {
		x = a[i].x_i, y = a[i].y_i, z = a[i].z_i, w = a[i].w_i;
		int l = 0, r = New[x].size() - 1, res_1 = -1;
		while(l <= r) {
			int mid = l + r >> 1;
			if(New[x][mid].L_i <= y && y <= New[x][mid].R_i) {
				res_1 = mid;
				break;
			}
			if(New[x][mid].L_i > y) r = mid - 1;
			else l = mid + 1;
		}
		if(res_1 != -1) y = New[x][res_1].R_i;
		l = 0, r = New[z].size() - 1; int res_2 = -1;
		while(l <= r) {
			int mid = l + r >> 1;
			if(New[z][mid].L_i <= w && w <= New[z][mid].R_i) {
				res_2 = mid;
				break;
			}
			if(New[z][mid].L_i > w) r = mid - 1;
			else l = mid + 1;
		}
		if(res_2 != -1) w = New[z][res_2].L_i;
		if(y >= w) {
//			puts("-----");
			printf("%d\n", (x != z) + rev(a[i].w_i) - rev(a[i].y_i));
			continue;
		}
//		printf("--- %d %d %d %d\n", x, y, z, w);
//		printf("   %d %d %d %d\n", x, y, z, w);
		int tim = jmp(y, w);
//		printf("tim:%d\n", tim);
//		printf("%d\n", tim);
		if(tim == -1) puts("-1");
		else printf("%d\n", tim + rev(a[i].w_i) - rev(a[i].y_i));
	}
	return 0;
}

Submission Info

Submission Time
Task G - Elevators
User brain
Language C++ 20 (gcc 12.2)
Score 600
Code Size 4862 Byte
Status AC
Exec Time 710 ms
Memory 138376 KiB

Compile Error

Main.cpp: In function ‘void build(int, int, int)’:
Main.cpp:35:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   35 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function ‘void modify(int, int, int)’:
Main.cpp:54:24: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   54 |         int mid = l(p) + r(p) >> 1;
      |                        ^
Main.cpp: In function ‘int query(int, int)’:
Main.cpp:63:24: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   63 |         int mid = l(p) + r(p) >> 1;
      |                        ^
Main.cpp: In function ‘void solve(int, int)’:
Main.cpp:83:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<qu>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   83 |         if(pos == loc[x].size()) return ;
      |            ~~~~^~~~~~~~~~~~~~~~
Main.cpp:85:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<qu>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   85 |         while(pos < loc[x].size() - 1 && loc[x][pos + 1].L_i <= R) R = max(R, loc[x][pos + 1].R_i), pos ++;
      |               ~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:118:34: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<qu>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  118 |                 for(int j = 0; j < New[i].size(); j ++) New[i][j].L_i = Find(New[i][j].L_i), New[i][j].R_i = Find(New[i][j].R_i), modify(1, New[i][j].L_i, New[i][j].R_i);// printf("l:%d r:%d\n", New[i][j].L_i, New[i][j].R_i);
      |                                ~~^~~~~~~~~~~~~~~
Main.cpp:131:37: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  131 |                         int mid = l + r >> 1;
      |                                   ~~^~~
Main.cpp:142:37: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  142 |                         int mid = l + r >> 1;
      |                                   ~~^~~
Main.cpp:94:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |         scanf("%d%d%d", &n, &m, &Q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:95:52: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |         for(int i = 1, a, b, c; i <= m; i ++) scanf("%d%d%d", &a, &b, &c), loc[a].push_back({b, c});
      |                                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |                 scanf("%d%d%d%d", &a[i].x_i, &a[i].y_i, &a[i].z_i, &a[i].w_i);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 60
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt
Case Name Status Exec Time Memory
example_00.txt AC 2 ms 3648 KiB
example_01.txt AC 2 ms 3772 KiB
test_00.txt AC 268 ms 64180 KiB
test_01.txt AC 498 ms 109688 KiB
test_02.txt AC 368 ms 73700 KiB
test_03.txt AC 368 ms 74260 KiB
test_04.txt AC 200 ms 42452 KiB
test_05.txt AC 703 ms 137960 KiB
test_06.txt AC 701 ms 137912 KiB
test_07.txt AC 694 ms 138040 KiB
test_08.txt AC 689 ms 138004 KiB
test_09.txt AC 697 ms 138008 KiB
test_10.txt AC 638 ms 138312 KiB
test_11.txt AC 628 ms 138268 KiB
test_12.txt AC 623 ms 138312 KiB
test_13.txt AC 624 ms 138260 KiB
test_14.txt AC 616 ms 138352 KiB
test_15.txt AC 624 ms 138280 KiB
test_16.txt AC 624 ms 138200 KiB
test_17.txt AC 622 ms 138376 KiB
test_18.txt AC 708 ms 134324 KiB
test_19.txt AC 710 ms 134404 KiB
test_20.txt AC 703 ms 134296 KiB
test_21.txt AC 707 ms 134156 KiB
test_22.txt AC 525 ms 114772 KiB
test_23.txt AC 531 ms 114828 KiB
test_24.txt AC 530 ms 114800 KiB
test_25.txt AC 527 ms 114864 KiB
test_26.txt AC 77 ms 8368 KiB
test_27.txt AC 75 ms 8272 KiB
test_28.txt AC 78 ms 8208 KiB
test_29.txt AC 76 ms 8440 KiB
test_30.txt AC 77 ms 8320 KiB
test_31.txt AC 76 ms 8360 KiB
test_32.txt AC 78 ms 8204 KiB
test_33.txt AC 77 ms 8244 KiB
test_34.txt AC 684 ms 135840 KiB
test_35.txt AC 676 ms 136192 KiB
test_36.txt AC 676 ms 135912 KiB
test_37.txt AC 677 ms 135936 KiB
test_38.txt AC 677 ms 135920 KiB
test_39.txt AC 681 ms 135912 KiB
test_40.txt AC 677 ms 135900 KiB
test_41.txt AC 677 ms 135920 KiB
test_42.txt AC 390 ms 83860 KiB
test_43.txt AC 391 ms 84012 KiB
test_44.txt AC 388 ms 83968 KiB
test_45.txt AC 388 ms 83900 KiB
test_46.txt AC 389 ms 83920 KiB
test_47.txt AC 387 ms 83904 KiB
test_48.txt AC 389 ms 84020 KiB
test_49.txt AC 383 ms 84032 KiB
test_50.txt AC 487 ms 115024 KiB
test_51.txt AC 485 ms 114904 KiB
test_52.txt AC 501 ms 115004 KiB
test_53.txt AC 490 ms 114984 KiB
test_54.txt AC 488 ms 114988 KiB
test_55.txt AC 488 ms 114904 KiB
test_56.txt AC 514 ms 115240 KiB
test_57.txt AC 525 ms 114968 KiB