# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52488 |
2018-06-26T05:54:52 Z |
강태규(#1363) |
Pinball (JOI14_pinball) |
C++11 |
|
542 ms |
32892 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
const llong inf = 1e16;
int sz;
struct seg {
llong dat[1 << 11];
seg() {
for (int i = 0; i < (1 << 11); ++i) {
dat[i] = inf;
}
}
void update(int i, int s, int e, int x, llong v) {
if (s == e) {
dat[i] = min(dat[i], v);
return;
}
int m = (s + e) / 2;
if (x <= m) update(i << 1, s, m, x, v);
else update(i << 1 | 1, m + 1, e, x, v);
dat[i] = min(dat[i << 1], dat[i << 1 | 1]);
}
void update(int x, llong v) {
update(1, 0, sz, x, v);
}
llong query(int i, int s, int e, int x, int y) const {
if (e < x || y < s) return inf;
if (x <= s && e <= y) return dat[i];
int m = (s + e) / 2;
return min(query(i << 1, s, m, x, y)
, query(i << 1 | 1, m + 1, e, x, y));
}
llong query(int x, int y) const {
return query(1, 0, sz, x, y);
}
} lseg[1003], rseg[1003];
int m, n;
int a[100001], b[100001], c[100001], d[100001];
vector<int> comp;
int find(int x) {
return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
}
int main() {
scanf("%d%d", &m, &n);
if (m > 1000) return 0;
for (int i = m; i--; ) {
scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
comp.push_back(c[i]);
}
comp.push_back(1);
comp.push_back(n);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
sz = comp.size() - 1;
for (int i = 0; i < m; ++i) {
a[i] = find(a[i]);
b[i] = find(b[i] + 1) - 1;
c[i] = find(c[i]);
}
for (int i = 0; i <= sz; ++i) {
lseg[i].update(i, 0);
rseg[i].update(i, 0);
}
for (int i = 0; i < m; ++i) {
llong v = inf;
for (int j = a[i]; j <= c[i]; ++j) {
v = min(v, lseg[j].query(c[i], b[i]));
}
v += d[i];
lseg[a[i]].update(b[i], v);
rseg[b[i]].update(a[i], v);
for (int j = b[i] + 1; j <= sz; ++j) {
v = rseg[j].query(a[i], c[i]) + d[i];
rseg[j].update(a[i], v);
lseg[a[i]].update(j, v);
}
for (int j = 0; j < a[i]; ++j) {
v = lseg[j].query(c[i], b[i]) + d[i];
lseg[j].update(b[i], v);
rseg[b[i]].update(j, v);
}
}
llong ans = rseg[sz].query(0, 0);
printf("%lld\n", ans < inf ? ans : -1);
return 0;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &m, &n);
~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:68:14: 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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
32504 KB |
Output is correct |
2 |
Correct |
24 ms |
32504 KB |
Output is correct |
3 |
Correct |
27 ms |
32556 KB |
Output is correct |
4 |
Correct |
28 ms |
32556 KB |
Output is correct |
5 |
Correct |
25 ms |
32588 KB |
Output is correct |
6 |
Correct |
27 ms |
32588 KB |
Output is correct |
7 |
Correct |
24 ms |
32588 KB |
Output is correct |
8 |
Correct |
24 ms |
32644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
32504 KB |
Output is correct |
2 |
Correct |
24 ms |
32504 KB |
Output is correct |
3 |
Correct |
27 ms |
32556 KB |
Output is correct |
4 |
Correct |
28 ms |
32556 KB |
Output is correct |
5 |
Correct |
25 ms |
32588 KB |
Output is correct |
6 |
Correct |
27 ms |
32588 KB |
Output is correct |
7 |
Correct |
24 ms |
32588 KB |
Output is correct |
8 |
Correct |
24 ms |
32644 KB |
Output is correct |
9 |
Correct |
27 ms |
32720 KB |
Output is correct |
10 |
Correct |
27 ms |
32728 KB |
Output is correct |
11 |
Correct |
28 ms |
32740 KB |
Output is correct |
12 |
Correct |
32 ms |
32740 KB |
Output is correct |
13 |
Correct |
32 ms |
32740 KB |
Output is correct |
14 |
Correct |
32 ms |
32744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
32504 KB |
Output is correct |
2 |
Correct |
24 ms |
32504 KB |
Output is correct |
3 |
Correct |
27 ms |
32556 KB |
Output is correct |
4 |
Correct |
28 ms |
32556 KB |
Output is correct |
5 |
Correct |
25 ms |
32588 KB |
Output is correct |
6 |
Correct |
27 ms |
32588 KB |
Output is correct |
7 |
Correct |
24 ms |
32588 KB |
Output is correct |
8 |
Correct |
24 ms |
32644 KB |
Output is correct |
9 |
Correct |
27 ms |
32720 KB |
Output is correct |
10 |
Correct |
27 ms |
32728 KB |
Output is correct |
11 |
Correct |
28 ms |
32740 KB |
Output is correct |
12 |
Correct |
32 ms |
32740 KB |
Output is correct |
13 |
Correct |
32 ms |
32740 KB |
Output is correct |
14 |
Correct |
32 ms |
32744 KB |
Output is correct |
15 |
Correct |
26 ms |
32744 KB |
Output is correct |
16 |
Correct |
36 ms |
32744 KB |
Output is correct |
17 |
Correct |
234 ms |
32744 KB |
Output is correct |
18 |
Correct |
29 ms |
32744 KB |
Output is correct |
19 |
Correct |
367 ms |
32796 KB |
Output is correct |
20 |
Correct |
145 ms |
32796 KB |
Output is correct |
21 |
Correct |
119 ms |
32892 KB |
Output is correct |
22 |
Correct |
542 ms |
32892 KB |
Output is correct |
23 |
Correct |
353 ms |
32892 KB |
Output is correct |
24 |
Correct |
460 ms |
32892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
32504 KB |
Output is correct |
2 |
Correct |
24 ms |
32504 KB |
Output is correct |
3 |
Correct |
27 ms |
32556 KB |
Output is correct |
4 |
Correct |
28 ms |
32556 KB |
Output is correct |
5 |
Correct |
25 ms |
32588 KB |
Output is correct |
6 |
Correct |
27 ms |
32588 KB |
Output is correct |
7 |
Correct |
24 ms |
32588 KB |
Output is correct |
8 |
Correct |
24 ms |
32644 KB |
Output is correct |
9 |
Correct |
27 ms |
32720 KB |
Output is correct |
10 |
Correct |
27 ms |
32728 KB |
Output is correct |
11 |
Correct |
28 ms |
32740 KB |
Output is correct |
12 |
Correct |
32 ms |
32740 KB |
Output is correct |
13 |
Correct |
32 ms |
32740 KB |
Output is correct |
14 |
Correct |
32 ms |
32744 KB |
Output is correct |
15 |
Correct |
26 ms |
32744 KB |
Output is correct |
16 |
Correct |
36 ms |
32744 KB |
Output is correct |
17 |
Correct |
234 ms |
32744 KB |
Output is correct |
18 |
Correct |
29 ms |
32744 KB |
Output is correct |
19 |
Correct |
367 ms |
32796 KB |
Output is correct |
20 |
Correct |
145 ms |
32796 KB |
Output is correct |
21 |
Correct |
119 ms |
32892 KB |
Output is correct |
22 |
Correct |
542 ms |
32892 KB |
Output is correct |
23 |
Correct |
353 ms |
32892 KB |
Output is correct |
24 |
Correct |
460 ms |
32892 KB |
Output is correct |
25 |
Incorrect |
27 ms |
32892 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |