oj.uz

Submission #258982

# Submission time Handle Problem Language Result Execution time Memory
258982 2020-08-06T22:34:07 Z Bruteforceman Treatment Project (JOI20_treatment) C++11
39 / 100
 3000 ms 253180 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const long long inf = 1e16;
long long d[maxn];
struct data {
  int t, l, r, c;
} a[maxn];
int n;
bool done[maxn];

int leftAfter(int x, int t) {
  if(x == 1) return 1;
  return x + t;
}
int rightAfter(int x, int t) {
  if(x == n) return n;
  return x - t;
}

bool isEdge(data p, data q) {
  if(p.t <= q.t) {
    return q.l + q.t <= p.r + p.t;
  } else {
    return q.l - q.t <= p.r - p.t;
  }
}

struct ds {
  set <pair <int, int>> t[maxn * 4];
  ds () {}
  void add(int x, int y, int idx, int c, int b, int e) {
    t[c].insert(make_pair(y, idx));
    if(b == e) {
      return ;
    }
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    if(x <= m) add(x, y, idx, l, b, m);
    else add(x, y, idx, r, m + 1, e);
  }
  void get(int x, int y, int val, vector <int> &v, int c, int b, int e) {
    if(x > y) return ;
    if(x <= b && e <= y) {
      while(!t[c].empty() && t[c].begin() -> first <= val) {
        v.push_back(t[c].begin() -> second);
        t[c].erase(t[c].begin());
      }
      return ;
    }
    if(y < b || e < x) return ;
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    get(x, y, val, v, l, b, m);
    get(x, y, val, v, r, m + 1, e);
  }
} S, T;


int main() {
  int m;
  scanf("%d %d", &n, &m);
  map <int, int> cmp;
  for(int i = 1; i <= m; i++) {
    scanf("%d %d %d %d", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
    a[i].l -= 1;
    cmp[a[i].t];
  }
  int idx = 0;
  for(auto &i : cmp) i.second = ++idx;
  priority_queue <pair <long long, int>, 
                  vector <pair <long long, int>>,
                  greater <pair <long long, int>>> Q;
  for(int i = 1; i <= m; i++) {
    if(a[i].l == 0) {
      d[i] = a[i].c;
      Q.emplace(d[i], i);
    } else {
      d[i] = inf;
    }
    S.add(cmp[a[i].t], a[i].l - a[i].t, i, 1, 1, idx);
    T.add(cmp[a[i].t], a[i].l + a[i].t, i, 1, 1, idx);
  }
  while(!Q.empty()) {
    int node = Q.top().second;
    long long dist = Q.top().first;
    Q.pop();
    if(done[node]) continue;
    done[node] = true;
    vector <int> v;
    S.get(1, cmp[a[node].t], a[node].r - a[node].t, v, 1, 1, idx);
    T.get(cmp[a[node].t], idx, a[node].r + a[node].t, v, 1, 1, idx);
    for(int i : v) {
      if(d[i] > d[node] + a[i].c) {
        d[i] = d[node] + a[i].c;
        Q.emplace(d[i], i);
      }
    }
  }
  long long ans = inf;
  for(int i = 1; i <= m; i++) {
    if(a[i].r == n) ans = min(ans, d[i]);
  }
  if(ans == inf) ans = -1;
  printf("%lld\n", ans);
  return 0;
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:88:15: warning: unused variable 'dist' [-Wunused-variable]
     long long dist = Q.top().first;
               ^~~~
treatment.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 88692 KB Output is correct
2 Correct 181 ms 90596 KB Output is correct
3 Correct 185 ms 91052 KB Output is correct
4 Correct 200 ms 90536 KB Output is correct
5 Correct 164 ms 92652 KB Output is correct
6 Correct 144 ms 90676 KB Output is correct
7 Correct 155 ms 90488 KB Output is correct
8 Correct 138 ms 90428 KB Output is correct
9 Correct 132 ms 90360 KB Output is correct
10 Correct 126 ms 90360 KB Output is correct
11 Correct 214 ms 93168 KB Output is correct
12 Correct 272 ms 93224 KB Output is correct
13 Correct 211 ms 92776 KB Output is correct
14 Correct 230 ms 92652 KB Output is correct
15 Correct 219 ms 90488 KB Output is correct
16 Correct 218 ms 90636 KB Output is correct
17 Correct 190 ms 89848 KB Output is correct
18 Correct 199 ms 92400 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 75512 KB Output is correct
2 Correct 45 ms 75512 KB Output is correct
3 Correct 52 ms 75512 KB Output is correct
4 Correct 44 ms 75520 KB Output is correct
5 Correct 44 ms 75512 KB Output is correct
6 Correct 42 ms 75512 KB Output is correct
7 Correct 53 ms 75512 KB Output is correct
8 Correct 51 ms 75516 KB Output is correct
9 Correct 52 ms 75512 KB Output is correct
10 Correct 43 ms 75512 KB Output is correct
11 Correct 52 ms 75512 KB Output is correct
12 Correct 43 ms 75640 KB Output is correct
13 Correct 43 ms 75512 KB Output is correct
14 Correct 53 ms 75512 KB Output is correct
15 Correct 43 ms 75512 KB Output is correct
16 Correct 52 ms 75512 KB Output is correct
17 Correct 54 ms 75512 KB Output is correct
18 Correct 42 ms 75512 KB Output is correct
19 Correct 53 ms 75512 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 75512 KB Output is correct
2 Correct 45 ms 75512 KB Output is correct
3 Correct 52 ms 75512 KB Output is correct
4 Correct 44 ms 75520 KB Output is correct
5 Correct 44 ms 75512 KB Output is correct
6 Correct 42 ms 75512 KB Output is correct
7 Correct 53 ms 75512 KB Output is correct
8 Correct 51 ms 75516 KB Output is correct
9 Correct 52 ms 75512 KB Output is correct
10 Correct 43 ms 75512 KB Output is correct
11 Correct 52 ms 75512 KB Output is correct
12 Correct 43 ms 75640 KB Output is correct
13 Correct 43 ms 75512 KB Output is correct
14 Correct 53 ms 75512 KB Output is correct
15 Correct 43 ms 75512 KB Output is correct
16 Correct 52 ms 75512 KB Output is correct
17 Correct 54 ms 75512 KB Output is correct
18 Correct 42 ms 75512 KB Output is correct
19 Correct 53 ms 75512 KB Output is correct
20 Correct 84 ms 81716 KB Output is correct
21 Correct 84 ms 81656 KB Output is correct
22 Correct 78 ms 80576 KB Output is correct
23 Correct 89 ms 80504 KB Output is correct
24 Correct 99 ms 82352 KB Output is correct
25 Correct 103 ms 82296 KB Output is correct
26 Correct 101 ms 82296 KB Output is correct
27 Correct 99 ms 82296 KB Output is correct
28 Correct 103 ms 82424 KB Output is correct
29 Correct 87 ms 82296 KB Output is correct
30 Correct 84 ms 82300 KB Output is correct
31 Correct 85 ms 82248 KB Output is correct
32 Correct 93 ms 82552 KB Output is correct
33 Correct 103 ms 82552 KB Output is correct
34 Correct 91 ms 81912 KB Output is correct
35 Correct 118 ms 82424 KB Output is correct
36 Correct 95 ms 82424 KB Output is correct
37 Correct 92 ms 81912 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 88692 KB Output is correct
2 Correct 181 ms 90596 KB Output is correct
3 Correct 185 ms 91052 KB Output is correct
4 Correct 200 ms 90536 KB Output is correct
5 Correct 164 ms 92652 KB Output is correct
6 Correct 144 ms 90676 KB Output is correct
7 Correct 155 ms 90488 KB Output is correct
8 Correct 138 ms 90428 KB Output is correct
9 Correct 132 ms 90360 KB Output is correct
10 Correct 126 ms 90360 KB Output is correct
11 Correct 214 ms 93168 KB Output is correct
12 Correct 272 ms 93224 KB Output is correct
13 Correct 211 ms 92776 KB Output is correct
14 Correct 230 ms 92652 KB Output is correct
15 Correct 219 ms 90488 KB Output is correct
16 Correct 218 ms 90636 KB Output is correct
17 Correct 190 ms 89848 KB Output is correct
18 Correct 199 ms 92400 KB Output is correct
19 Correct 54 ms 75512 KB Output is correct
20 Correct 45 ms 75512 KB Output is correct
21 Correct 52 ms 75512 KB Output is correct
22 Correct 44 ms 75520 KB Output is correct
23 Correct 44 ms 75512 KB Output is correct
24 Correct 42 ms 75512 KB Output is correct
25 Correct 53 ms 75512 KB Output is correct
26 Correct 51 ms 75516 KB Output is correct
27 Correct 52 ms 75512 KB Output is correct
28 Correct 43 ms 75512 KB Output is correct
29 Correct 52 ms 75512 KB Output is correct
30 Correct 43 ms 75640 KB Output is correct
31 Correct 43 ms 75512 KB Output is correct
32 Correct 53 ms 75512 KB Output is correct
33 Correct 43 ms 75512 KB Output is correct
34 Correct 52 ms 75512 KB Output is correct
35 Correct 54 ms 75512 KB Output is correct
36 Correct 42 ms 75512 KB Output is correct
37 Correct 53 ms 75512 KB Output is correct
38 Correct 84 ms 81716 KB Output is correct
39 Correct 84 ms 81656 KB Output is correct
40 Correct 78 ms 80576 KB Output is correct
41 Correct 89 ms 80504 KB Output is correct
42 Correct 99 ms 82352 KB Output is correct
43 Correct 103 ms 82296 KB Output is correct
44 Correct 101 ms 82296 KB Output is correct
45 Correct 99 ms 82296 KB Output is correct
46 Correct 103 ms 82424 KB Output is correct
47 Correct 87 ms 82296 KB Output is correct
48 Correct 84 ms 82300 KB Output is correct
49 Correct 85 ms 82248 KB Output is correct
50 Correct 93 ms 82552 KB Output is correct
51 Correct 103 ms 82552 KB Output is correct
52 Correct 91 ms 81912 KB Output is correct
53 Correct 118 ms 82424 KB Output is correct
54 Correct 95 ms 82424 KB Output is correct
55 Correct 92 ms 81912 KB Output is correct
56 Correct 2664 ms 240992 KB Output is correct
57 Correct 2660 ms 241484 KB Output is correct
58 Correct 2447 ms 239956 KB Output is correct
59 Correct 2484 ms 240488 KB Output is correct
60 Correct 2172 ms 217480 KB Output is correct
61 Correct 2158 ms 240168 KB Output is correct
62 Correct 2654 ms 240860 KB Output is correct
63 Correct 2430 ms 252804 KB Output is correct
64 Correct 2152 ms 252672 KB Output is correct
65 Correct 371 ms 100064 KB Output is correct
66 Correct 1953 ms 216872 KB Output is correct
67 Correct 2497 ms 253048 KB Output is correct
68 Correct 2023 ms 253176 KB Output is correct
69 Correct 1605 ms 251456 KB Output is correct
70 Correct 2984 ms 253180 KB Output is correct
71 Correct 2181 ms 253132 KB Output is correct
72 Correct 1697 ms 252904 KB Output is correct
73 Correct 2931 ms 252968 KB Output is correct
74 Correct 1732 ms 252664 KB Output is correct
75 Correct 1440 ms 252740 KB Output is correct
76 Execution timed out 3087 ms 246316 KB Time limit exceeded
77 Halted 0 ms 0 KB -