# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52340 |
2018-06-25T13:01:28 Z |
Costin Andrei Oncescu(#1295) |
Pinball (JOI14_pinball) |
C++11 |
|
537 ms |
60632 KB |
#include<bits/stdc++.h>
using namespace std;
int N, M, A[100009], B[100009], C[100009], D[100009];
long long aib[2][300009], ans;
const long long INF = 1LL << 60;
map < int, int > mp;
void read ()
{
vector < int > nrm;
scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
scanf ("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]),
nrm.push_back (A[i]), nrm.push_back (B[i]), nrm.push_back (C[i]);
nrm.push_back (1), nrm.push_back (M), sort (nrm.begin (), nrm.end ());
nrm.erase (unique (nrm.begin (), nrm.end ()), nrm.end ()), M = nrm.size ();
for (int i=0; i<M; i++)
mp[nrm[i]] = i + 1;
for (int i=1; i<=N; i++)
A[i] = mp[A[i]], B[i] = mp[B[i]], C[i] = mp[C[i]];
}
void initializeAIB ()
{
for (int i=0; i<2; i++)
for (int j=0; j<=M; j++)
aib[i][j] = INF;
}
void update (int lin, int pos, long long val)
{
while (pos <= M)
aib[lin][pos] = min (aib[lin][pos], val),
pos += pos - (pos & (pos - 1));
}
long long query (int lin, int pos)
{
long long ans = INF;
while (pos)
ans = min (ans, aib[lin][pos]),
pos &= pos - 1;
return ans;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
read (), ans = INF;
initializeAIB ();
update (0, M, 0);
update (1, M, 0);
for (int i=1; i<=N; i++)
{
long long x = query (0, M - A[i] + 1), y = query (1, B[i]);
update (0, M - C[i] + 1, x + D[i]);
update (1, C[i], y + D[i]);
if (x + y + D[i] < ans)
ans = x + y + D[i];
}
if (ans >= INF)
ans = -1;
printf ("%lld\n", ans);
return 0;
}
Compilation message
pinball.cpp: In function 'void read()':
pinball.cpp:13:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &N, &M);
~~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:16:51: 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]),
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nrm.push_back (A[i]), nrm.push_back (B[i]), nrm.push_back (C[i]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
2 ms |
540 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
2 ms |
540 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
636 KB |
Output is correct |
10 |
Correct |
3 ms |
644 KB |
Output is correct |
11 |
Correct |
3 ms |
668 KB |
Output is correct |
12 |
Correct |
2 ms |
692 KB |
Output is correct |
13 |
Correct |
3 ms |
764 KB |
Output is correct |
14 |
Correct |
3 ms |
776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
2 ms |
540 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
636 KB |
Output is correct |
10 |
Correct |
3 ms |
644 KB |
Output is correct |
11 |
Correct |
3 ms |
668 KB |
Output is correct |
12 |
Correct |
2 ms |
692 KB |
Output is correct |
13 |
Correct |
3 ms |
764 KB |
Output is correct |
14 |
Correct |
3 ms |
776 KB |
Output is correct |
15 |
Correct |
3 ms |
776 KB |
Output is correct |
16 |
Correct |
3 ms |
792 KB |
Output is correct |
17 |
Correct |
4 ms |
932 KB |
Output is correct |
18 |
Correct |
5 ms |
932 KB |
Output is correct |
19 |
Correct |
4 ms |
1140 KB |
Output is correct |
20 |
Correct |
4 ms |
1140 KB |
Output is correct |
21 |
Correct |
3 ms |
1164 KB |
Output is correct |
22 |
Correct |
4 ms |
1308 KB |
Output is correct |
23 |
Correct |
5 ms |
1348 KB |
Output is correct |
24 |
Correct |
5 ms |
1388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
2 ms |
540 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
636 KB |
Output is correct |
10 |
Correct |
3 ms |
644 KB |
Output is correct |
11 |
Correct |
3 ms |
668 KB |
Output is correct |
12 |
Correct |
2 ms |
692 KB |
Output is correct |
13 |
Correct |
3 ms |
764 KB |
Output is correct |
14 |
Correct |
3 ms |
776 KB |
Output is correct |
15 |
Correct |
3 ms |
776 KB |
Output is correct |
16 |
Correct |
3 ms |
792 KB |
Output is correct |
17 |
Correct |
4 ms |
932 KB |
Output is correct |
18 |
Correct |
5 ms |
932 KB |
Output is correct |
19 |
Correct |
4 ms |
1140 KB |
Output is correct |
20 |
Correct |
4 ms |
1140 KB |
Output is correct |
21 |
Correct |
3 ms |
1164 KB |
Output is correct |
22 |
Correct |
4 ms |
1308 KB |
Output is correct |
23 |
Correct |
5 ms |
1348 KB |
Output is correct |
24 |
Correct |
5 ms |
1388 KB |
Output is correct |
25 |
Correct |
22 ms |
2704 KB |
Output is correct |
26 |
Correct |
88 ms |
6128 KB |
Output is correct |
27 |
Correct |
323 ms |
12380 KB |
Output is correct |
28 |
Correct |
145 ms |
12380 KB |
Output is correct |
29 |
Correct |
177 ms |
17188 KB |
Output is correct |
30 |
Correct |
191 ms |
18136 KB |
Output is correct |
31 |
Correct |
442 ms |
30428 KB |
Output is correct |
32 |
Correct |
397 ms |
31316 KB |
Output is correct |
33 |
Correct |
52 ms |
31316 KB |
Output is correct |
34 |
Correct |
234 ms |
34936 KB |
Output is correct |
35 |
Correct |
294 ms |
49128 KB |
Output is correct |
36 |
Correct |
537 ms |
52940 KB |
Output is correct |
37 |
Correct |
468 ms |
56764 KB |
Output is correct |
38 |
Correct |
450 ms |
60632 KB |
Output is correct |