oj.uz

Submission #25266

# Submission time Handle Problem Language Result Execution time Memory
25266 2017-06-21T05:27:58 Z kajebiii Pinball (JOI14_pinball) C++14
100 / 100
 286 ms 22108 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

int N, M;
struct IDX {
	int P; vector<ll> val;
	IDX(int n) {
		for(P=1; P<n; P<<=1);
		val = vector<ll>(2*P, LINF);
	}
	void update(int v, ll k) {
		if(val[v+=P] <= k) return;
		val[v] = k;
		while(v/=2) val[v] = min(val[v*2], val[v*2+1]);
	}
	ll getMin(int a, int b) {
		a+=P, b+=P;
		ll res = LINF;
		while(a<=b) {
			if(a%2==1) res = min(res, val[a++]);
			if(b%2==0) res = min(res, val[b--]);
			a>>=1;b>>=1;
		}
		return res;
	}
};

const int MAX_N = 1e5 + 100;

int Nr[MAX_N][4];
vector<int> Co;
int main() {
	cin >> N >> M;
	REP(i, N) REP(j, 4) {
		scanf("%d", &Nr[i][j]);
		if(j < 3) Co.push_back(Nr[i][j]);
	}
	Co.push_back(1), Co.push_back(M);
	sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());
	REP(i, N) REP(j, 3) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin();
	IDX idx[2] = {IDX(SZ(Co)), IDX(SZ(Co))};

	idx[0].update(0, 0ll); idx[1].update(SZ(Co)-1, 0ll);

	ll ans = LINF;
	REP(i, N) {
		int a = Nr[i][0], b = Nr[i][1], c = Nr[i][2], d = Nr[i][3];
		ans = min(ans, idx[0].getMin(a, b) + idx[1].getMin(a, b) + d);
		idx[0].update(c, idx[0].getMin(a, b) + d);
		idx[1].update(c, idx[1].getMin(a, b) + d);
	}
	if(ans == LINF) ans = -1;
	printf("%lld\n", ans);
	return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:47:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Nr[i][j]);
                         ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Correct 0 ms 3588 KB Output is correct
5 Correct 0 ms 3588 KB Output is correct
6 Correct 0 ms 3588 KB Output is correct
7 Correct 0 ms 3588 KB Output is correct
8 Correct 0 ms 3588 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Correct 0 ms 3588 KB Output is correct
5 Correct 0 ms 3588 KB Output is correct
6 Correct 0 ms 3588 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3728 KB Output is correct
4 Correct 0 ms 3588 KB Output is correct
5 Correct 0 ms 3760 KB Output is correct
6 Correct 0 ms 3588 KB Output is correct
7 Correct 0 ms 3744 KB Output is correct
8 Correct 0 ms 3760 KB Output is correct
9 Correct 0 ms 3760 KB Output is correct
10 Correct 3 ms 3760 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4828 KB Output is correct
2 Correct 59 ms 6236 KB Output is correct
3 Correct 186 ms 8796 KB Output is correct
4 Correct 179 ms 6744 KB Output is correct
5 Correct 129 ms 8796 KB Output is correct
6 Correct 186 ms 6744 KB Output is correct
7 Correct 286 ms 13916 KB Output is correct
8 Correct 243 ms 9820 KB Output is correct
9 Correct 26 ms 5980 KB Output is correct
10 Correct 119 ms 12892 KB Output is correct
11 Correct 126 ms 22108 KB Output is correct
12 Correct 279 ms 22108 KB Output is correct
13 Correct 189 ms 22108 KB Output is correct
14 Correct 179 ms 22108 KB Output is correct