답안 #708159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708159 2023-03-11T07:22:14 Z Dan4Life Pinball (JOI14_pinball) C++17
100 / 100
378 ms 34376 KB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define int long long
const int mxN = (int)2e5+10, LINF = (int)1e18;
int n, m, a[mxN], b[mxN], c[mxN], d[mxN];
unordered_map<int,int> ind;
int segTree[2][4*mxN];
vector<int> v;
int mxM;

void upd(int i, int v, int t, int p=0, int l=0, int r=mxM){
	if(l==r){ segTree[t][p]=min(segTree[t][p],v); return; }
	int mid = (l+r)/2; int lp = p+1, rp = p+2*(mid-l+1);
	if(i<=mid) upd(i,v,t,lp,l,mid);
	else upd(i,v,t,rp,mid+1,r);
	segTree[t][p] = min(segTree[t][lp],segTree[t][rp]);
}

int query(int i, int j, int t, int p=0, int l=0, int r=mxM){
	if(i>r or j<l or i>j) return LINF;
	if(i<=l and r<=j) return segTree[t][p];
	int mid = (l+r)/2; int lp = p+1, rp = p+2*(mid-l+1);
	return min(query(i,j,t,lp,l,mid),query(i,j,t,rp,mid+1,r));
} 

main() {
	cin >> m >> n; int ans = LINF;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		v.pb(a[i]), v.pb(b[i]), v.pb(c[i]);
	} v.pb(1), v.pb(n);
	sort(all(v)); v.erase(unique(all(v)),v.end());
	for(int x = 0; auto u : v) ind[u]=x++; mxM = sz(v);
	for(int i = 1; i <= m; i++) a[i]=ind[a[i]],b[i]=ind[b[i]],c[i]=ind[c[i]];
	for(int i = 0; i < 2; i++) fill(segTree[i],segTree[i]+mxN*4,LINF);
	upd(0,0,0), upd(sz(v)-1,0,1);
	for(int i = 1; i <= m; i++){
		int L = query(a[i],b[i],0)+d[i]; upd(c[i],L,0); 
		int R = query(a[i],b[i],1)+d[i]; upd(c[i],R,1);
		ans = min(ans, L+R-d[i]);
	}
	cout << (ans==LINF?-1:ans) << "\n";
}

Compilation message

pinball.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main() {
      | ^~~~
pinball.cpp: In function 'int main()':
pinball.cpp:36:17: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   36 |  for(int x = 0; auto u : v) ind[u]=x++; mxM = sz(v);
      |                 ^~~~
pinball.cpp:36:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |  for(int x = 0; auto u : v) ind[u]=x++; mxM = sz(v);
      |  ^~~
pinball.cpp:36:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   36 |  for(int x = 0; auto u : v) ind[u]=x++; mxM = sz(v);
      |                                         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 5 ms 12756 KB Output is correct
6 Correct 6 ms 12756 KB Output is correct
7 Correct 6 ms 12756 KB Output is correct
8 Correct 6 ms 12756 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 5 ms 12756 KB Output is correct
6 Correct 6 ms 12756 KB Output is correct
7 Correct 6 ms 12756 KB Output is correct
8 Correct 6 ms 12756 KB Output is correct
9 Correct 6 ms 12884 KB Output is correct
10 Correct 6 ms 12884 KB Output is correct
11 Correct 6 ms 12868 KB Output is correct
12 Correct 6 ms 12884 KB Output is correct
13 Correct 6 ms 12864 KB Output is correct
14 Correct 5 ms 12884 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 5 ms 12756 KB Output is correct
6 Correct 6 ms 12756 KB Output is correct
7 Correct 6 ms 12756 KB Output is correct
8 Correct 6 ms 12756 KB Output is correct
9 Correct 6 ms 12884 KB Output is correct
10 Correct 6 ms 12884 KB Output is correct
11 Correct 6 ms 12868 KB Output is correct
12 Correct 6 ms 12884 KB Output is correct
13 Correct 6 ms 12864 KB Output is correct
14 Correct 5 ms 12884 KB Output is correct
15 Correct 6 ms 12756 KB Output is correct
16 Correct 7 ms 12884 KB Output is correct
17 Correct 9 ms 13012 KB Output is correct
18 Correct 8 ms 12872 KB Output is correct
19 Correct 9 ms 13072 KB Output is correct
20 Correct 9 ms 12916 KB Output is correct
21 Correct 7 ms 12884 KB Output is correct
22 Correct 9 ms 13012 KB Output is correct
23 Correct 8 ms 13088 KB Output is correct
24 Correct 8 ms 13012 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 5 ms 12756 KB Output is correct
6 Correct 6 ms 12756 KB Output is correct
7 Correct 6 ms 12756 KB Output is correct
8 Correct 6 ms 12756 KB Output is correct
9 Correct 6 ms 12884 KB Output is correct
10 Correct 6 ms 12884 KB Output is correct
11 Correct 6 ms 12868 KB Output is correct
12 Correct 6 ms 12884 KB Output is correct
13 Correct 6 ms 12864 KB Output is correct
14 Correct 5 ms 12884 KB Output is correct
15 Correct 6 ms 12756 KB Output is correct
16 Correct 7 ms 12884 KB Output is correct
17 Correct 9 ms 13012 KB Output is correct
18 Correct 8 ms 12872 KB Output is correct
19 Correct 9 ms 13072 KB Output is correct
20 Correct 9 ms 12916 KB Output is correct
21 Correct 7 ms 12884 KB Output is correct
22 Correct 9 ms 13012 KB Output is correct
23 Correct 8 ms 13088 KB Output is correct
24 Correct 8 ms 13012 KB Output is correct
25 Correct 32 ms 14288 KB Output is correct
26 Correct 75 ms 17448 KB Output is correct
27 Correct 214 ms 23780 KB Output is correct
28 Correct 252 ms 22152 KB Output is correct
29 Correct 161 ms 22188 KB Output is correct
30 Correct 264 ms 22928 KB Output is correct
31 Correct 322 ms 28808 KB Output is correct
32 Correct 315 ms 27224 KB Output is correct
33 Correct 56 ms 17056 KB Output is correct
34 Correct 156 ms 23556 KB Output is correct
35 Correct 325 ms 34372 KB Output is correct
36 Correct 363 ms 34308 KB Output is correct
37 Correct 378 ms 34376 KB Output is correct
38 Correct 335 ms 34228 KB Output is correct