Submission #56762

#	Time	Username	Problem	Language	Result	Execution time	Memory
56762		RezwanArefin01	Pinball (JOI14_pinball)	C++17	51 / 100	1089 ms	42588 KiB

pinball

#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 (stderr)

pinball.cpp: In function 'void update(int, int, int, int, ll)':
pinball.cpp:15: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:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1; 
          ~~^~~
pinball.cpp: In function 'int main(int, const char**)':
pinball.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
pinball.cpp:30: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:33: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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49