답안 #56763 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56763	2018-07-12T12:51:58 Z	RezwanArefin01	Pinball (JOI14_pinball)	C++17	51 / 100	1000 ms	42464 KB

pinball

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 
int n, m, a[N], b[N], c[N], d[N]; 
ll fl[N], fr[N], t[N * 12]; 

void update(int node, int l, int r, int i, ll v) {
	if(l == r) {
		t[node] = min(t[node], v); 
		return;
	} int m = l + r >> 1; 
	if(i <= m) update(node << 1, l, m, i, v); 
	else update(node << 1 | 1, m + 1, r, i, v); 
	t[node] = min(t[node << 1], t[node << 1 | 1]); 
}

ll query(int node, int l, int r, int i, int j) {
	if(r < i || l > j) return 1e15; 
	if(i <= l && r <= j) return t[node];
	int m = l + r >> 1; 
	return min(query(node << 1, l, m, i, j), 
			query(node << 1 | 1, m + 1, r, i, j)); 
}

int main(int argc, char const *argv[]) {
	scanf("%d %d", &m, &n); 
	vector<int> v;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]); 
		v.push_back(a[i]);
		v.push_back(b[i]);
		v.push_back(c[i]); 
	}	
	sort(v.begin(), v.end()); 
	v.erase(unique(v.begin(), v.end()), v.end());
	map<int, int> mp, rev; 

	for(int i = 0; i < v.size(); i++) {
		mp[v[i]] = i + 1; 
		rev[i + 1] = v[i]; 
	}
	for(int i = 1; i <= m; i++) {
		a[i] = mp[a[i]]; 
		b[i] = mp[b[i]]; 
		c[i] = mp[c[i]];
	}
	int L = mp.size() + 1; 
	for(int i = 0; i < 4 * L; i++) t[i] = 1e15; 
	for(int i = 1; i <= m; i++) {
		if(rev[a[i]] == 1) fl[i] = d[i]; 
		else fl[i] = query(1, 1, L, a[i], b[i]) + d[i]; 
		update(1, 1, L, c[i], fl[i]); 
	}
	for(int i = 0; i < 4 * L; i++) t[i] = 1e15; 
	for(int i = 1; i <= m; i++) {
		if(rev[b[i]] == n) fr[i] = d[i]; 
		else fr[i] = query(1, 1, L, a[i], b[i]) + d[i]; 
		update(1, 1, L, c[i], fr[i]);
	}
	ll ans = 1e18; 
	for(int i = 1; i <= m; i++) {
		ans = min(ans, fl[i] + fr[i] - d[i]); 
	}
	if(ans > 1e15) ans = -1; 
	printf("%lld\n", ans);

}

Compilation message

pinball.cpp: In function 'void update(int, int, int, int, ll)':
pinball.cpp:18:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  } int m = l + r >> 1; 
            ~~^~~
pinball.cpp: In function 'll query(int, int, int, int, int)':
pinball.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1; 
          ~~^~~
pinball.cpp: In function 'int main(int, const char**)':
pinball.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
pinball.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &m, &n); 
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	444 KB	Output is correct
3	Correct	2 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	444 KB	Output is correct
3	Correct	2 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	4 ms	648 KB	Output is correct
12	Correct	3 ms	684 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	3 ms	704 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	444 KB	Output is correct
3	Correct	2 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	4 ms	648 KB	Output is correct
12	Correct	3 ms	684 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	3 ms	704 KB	Output is correct
15	Correct	3 ms	704 KB	Output is correct
16	Correct	3 ms	704 KB	Output is correct
17	Correct	5 ms	748 KB	Output is correct
18	Correct	5 ms	748 KB	Output is correct
19	Correct	7 ms	1020 KB	Output is correct
20	Correct	6 ms	1020 KB	Output is correct
21	Correct	3 ms	1020 KB	Output is correct
22	Correct	6 ms	1024 KB	Output is correct
23	Correct	7 ms	1144 KB	Output is correct
24	Correct	8 ms	1144 KB	Output is correct

Subtask #4
0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	444 KB	Output is correct
3	Correct	2 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	2 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	2 ms	476 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	4 ms	648 KB	Output is correct
12	Correct	3 ms	684 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	3 ms	704 KB	Output is correct
15	Correct	3 ms	704 KB	Output is correct
16	Correct	3 ms	704 KB	Output is correct
17	Correct	5 ms	748 KB	Output is correct
18	Correct	5 ms	748 KB	Output is correct
19	Correct	7 ms	1020 KB	Output is correct
20	Correct	6 ms	1020 KB	Output is correct
21	Correct	3 ms	1020 KB	Output is correct
22	Correct	6 ms	1024 KB	Output is correct
23	Correct	7 ms	1144 KB	Output is correct
24	Correct	8 ms	1144 KB	Output is correct
25	Correct	63 ms	3196 KB	Output is correct
26	Correct	212 ms	8688 KB	Output is correct
27	Correct	566 ms	16456 KB	Output is correct
28	Correct	201 ms	16456 KB	Output is correct
29	Correct	501 ms	16456 KB	Output is correct
30	Correct	399 ms	16456 KB	Output is correct
31	Correct	954 ms	26028 KB	Output is correct
32	Correct	679 ms	26028 KB	Output is correct
33	Correct	99 ms	26028 KB	Output is correct
34	Correct	599 ms	26028 KB	Output is correct
35	Correct	698 ms	42416 KB	Output is correct
36	Execution timed out	1082 ms	42464 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

답안 #56763

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 49.0