oj.uz

Submission #25263

# Submission time Handle Problem Language Result Execution time Memory
25263 2017-06-21T05:23:56 Z kajebiii Pinball (JOI14_pinball) C++14
78 / 100
 299 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(N);
	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, 0); idx[1].update(SZ(Co)-1, 0);

	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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Incorrect 0 ms 3588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4828 KB Output is correct
2 Correct 59 ms 6236 KB Output is correct
3 Correct 216 ms 8796 KB Output is correct
4 Correct 153 ms 6744 KB Output is correct
5 Correct 129 ms 8796 KB Output is correct
6 Correct 229 ms 6744 KB Output is correct
7 Correct 263 ms 13916 KB Output is correct
8 Correct 236 ms 9820 KB Output is correct
9 Correct 29 ms 5980 KB Output is correct
10 Correct 106 ms 12892 KB Output is correct
11 Correct 149 ms 22108 KB Output is correct
12 Correct 299 ms 22108 KB Output is correct
13 Correct 226 ms 22108 KB Output is correct
14 Correct 209 ms 22108 KB Output is correct