oj.uz

Submission #1113219

# Submission time Handle Problem Language Result Execution time Memory
1113219 2024-11-16T04:14:38 Z VinhLuu Real Mountains (CCO23_day1problem2) C++17
18 / 25
 1826 ms 192748 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 5;
const int oo = 1e16;
const int mod = 1e6 + 3;

int n, a[N], pf[N], sf[N], st[N << 1], des[N], le[N], ri[N];

void update(int i,int x){
  i += n - 1;
  st[i] = x;
  while(i > 1){
    i /= 2;
    st[i] = min(st[i << 1], st[i << 1|1]);
  }
}

int get(int l,int r){
  if(l > r) return oo;
  r++;
  int ret = oo;
  for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
    if(l & 1) ret = min(ret, st[l ++]);
    if(r & 1) ret = min(ret, st[-- r]);
  }
  return ret;
}

void add(int &x,int y){
  x = (x + y) % mod;
}
vector<int> open[N], close[N];

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n;
  for(int i = 1; i <= n; i ++) cin >> a[i];

  for(int i = 1; i <= n; i ++){
    le[i] = le[i - 1] + (pf[i] > a[i] ? pf[i] - a[i] : 0);
    pf[i] = max(a[i], pf[i - 1]);
    update(i, a[i]);
  }
  for(int i = n; i >= 1; i --){
    ri[i] = ri[i + 1] + (sf[i] > a[i] ? sf[i] - a[i] : 0);
    sf[i] = max(sf[i + 1], a[i]);
  }
  int pos = 1, ans = oo;
  for(int i = 1; i <= n; i ++){
    int val = max(pf[i], sf[i]) - a[i] + le[i - 1] + ri[i + 1];
    if(val < ans){
      ans = val;
      pos = i;
    }
  }
  ans = 0;
  des[pos] = max(pf[pos], sf[pos]);
  for(int i = 1; i < pos; i ++) des[i] = pf[i];
  for(int i = pos + 1; i <= n; i ++) des[i] = sf[i];

  for(int i = 1; i <= n; i ++){
//    cerr << i << " " << a[i] << " " << des[i] << " p\n";
    if(a[i] < des[i]){
      open[a[i]].push_back(i);
    }
    close[des[i]].push_back(i);

  }

  ans = 0;

  set<int> col;

  for(int k = 1; k <= 1000000; k ++){
    for(auto j : close[k]){
      if(col.find(j) != col.end()) col.erase(j);
      update(j, oo);
    }
    for(auto j : open[k]){
      col.insert(j);
      update(j, oo);
    }
    if(col.empty()) continue;
    int x = (*col.begin());
    int y = (*col.rbegin());
    if(x == y){
      int val = get(1, x - 1) + get(x + 1, n) + k;
      add(ans, val);
    }else{
      int cx = get(1, x - 1) + get(x + 1, n) + k;
      int cy = get(1, y - 1) + get(y + 1, n) + k;
      int val = min(cx + 2 * k + 1 + get(y + 1, n), cy + 2 * k + 1 + get(1, x - 1));
      add(ans, val);
    }

    int cnt = (int)col.size();

    int val = max(0ll, cnt - 2) * (3 * k % mod + 2) % mod;
//    cerr << k << " " << ans << " " << val << " e\n";
    add(ans, val);
  }
  cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct
13 Correct 33 ms 47964 KB Output is correct
14 Correct 32 ms 47432 KB Output is correct
15 Correct 32 ms 47432 KB Output is correct
16 Correct 36 ms 47952 KB Output is correct
17 Correct 34 ms 47884 KB Output is correct
18 Correct 34 ms 48100 KB Output is correct
19 Correct 34 ms 48088 KB Output is correct
20 Correct 37 ms 48140 KB Output is correct
21 Correct 40 ms 47952 KB Output is correct
22 Correct 37 ms 47952 KB Output is correct
23 Correct 37 ms 48132 KB Output is correct
24 Correct 42 ms 47948 KB Output is correct
25 Correct 38 ms 47944 KB Output is correct
26 Correct 37 ms 47952 KB Output is correct
27 Correct 37 ms 47880 KB Output is correct
28 Correct 40 ms 47944 KB Output is correct
29 Correct 41 ms 47404 KB Output is correct
30 Correct 32 ms 47456 KB Output is correct
31 Correct 32 ms 47440 KB Output is correct
32 Correct 37 ms 47328 KB Output is correct
33 Correct 33 ms 47440 KB Output is correct
34 Correct 37 ms 47440 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct
13 Correct 33 ms 47964 KB Output is correct
14 Correct 32 ms 47432 KB Output is correct
15 Correct 32 ms 47432 KB Output is correct
16 Correct 36 ms 47952 KB Output is correct
17 Correct 34 ms 47884 KB Output is correct
18 Correct 34 ms 48100 KB Output is correct
19 Correct 34 ms 48088 KB Output is correct
20 Correct 37 ms 48140 KB Output is correct
21 Correct 40 ms 47952 KB Output is correct
22 Correct 37 ms 47952 KB Output is correct
23 Correct 37 ms 48132 KB Output is correct
24 Correct 42 ms 47948 KB Output is correct
25 Correct 38 ms 47944 KB Output is correct
26 Correct 37 ms 47952 KB Output is correct
27 Correct 37 ms 47880 KB Output is correct
28 Correct 40 ms 47944 KB Output is correct
29 Correct 41 ms 47404 KB Output is correct
30 Correct 32 ms 47456 KB Output is correct
31 Correct 32 ms 47440 KB Output is correct
32 Correct 37 ms 47328 KB Output is correct
33 Correct 33 ms 47440 KB Output is correct
34 Correct 37 ms 47440 KB Output is correct
35 Correct 94 ms 48216 KB Output is correct
36 Correct 93 ms 48200 KB Output is correct
37 Correct 90 ms 48212 KB Output is correct
38 Correct 91 ms 48200 KB Output is correct
39 Correct 93 ms 48200 KB Output is correct
40 Correct 89 ms 47964 KB Output is correct
41 Correct 80 ms 47944 KB Output is correct
42 Correct 82 ms 47952 KB Output is correct
43 Correct 106 ms 48220 KB Output is correct
44 Correct 110 ms 48200 KB Output is correct
45 Correct 109 ms 48052 KB Output is correct
46 Correct 97 ms 48000 KB Output is correct
47 Correct 97 ms 48204 KB Output is correct
48 Correct 101 ms 48204 KB Output is correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct
13 Correct 33 ms 47964 KB Output is correct
14 Correct 32 ms 47432 KB Output is correct
15 Correct 32 ms 47432 KB Output is correct
16 Correct 36 ms 47952 KB Output is correct
17 Correct 34 ms 47884 KB Output is correct
18 Correct 34 ms 48100 KB Output is correct
19 Correct 34 ms 48088 KB Output is correct
20 Correct 37 ms 48140 KB Output is correct
21 Correct 40 ms 47952 KB Output is correct
22 Correct 37 ms 47952 KB Output is correct
23 Correct 37 ms 48132 KB Output is correct
24 Correct 42 ms 47948 KB Output is correct
25 Correct 38 ms 47944 KB Output is correct
26 Correct 37 ms 47952 KB Output is correct
27 Correct 37 ms 47880 KB Output is correct
28 Correct 40 ms 47944 KB Output is correct
29 Correct 41 ms 47404 KB Output is correct
30 Correct 32 ms 47456 KB Output is correct
31 Correct 32 ms 47440 KB Output is correct
32 Correct 37 ms 47328 KB Output is correct
33 Correct 33 ms 47440 KB Output is correct
34 Correct 37 ms 47440 KB Output is correct
35 Correct 94 ms 48216 KB Output is correct
36 Correct 93 ms 48200 KB Output is correct
37 Correct 90 ms 48212 KB Output is correct
38 Correct 91 ms 48200 KB Output is correct
39 Correct 93 ms 48200 KB Output is correct
40 Correct 89 ms 47964 KB Output is correct
41 Correct 80 ms 47944 KB Output is correct
42 Correct 82 ms 47952 KB Output is correct
43 Correct 106 ms 48220 KB Output is correct
44 Correct 110 ms 48200 KB Output is correct
45 Correct 109 ms 48052 KB Output is correct
46 Correct 97 ms 48000 KB Output is correct
47 Correct 97 ms 48204 KB Output is correct
48 Correct 101 ms 48204 KB Output is correct
49 Runtime error 103 ms 96448 KB Execution killed with signal 11
50 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct
13 Correct 33 ms 47964 KB Output is correct
14 Correct 32 ms 47432 KB Output is correct
15 Correct 32 ms 47432 KB Output is correct
16 Correct 36 ms 47952 KB Output is correct
17 Correct 34 ms 47884 KB Output is correct
18 Correct 34 ms 48100 KB Output is correct
19 Correct 34 ms 48088 KB Output is correct
20 Correct 37 ms 48140 KB Output is correct
21 Correct 40 ms 47952 KB Output is correct
22 Correct 37 ms 47952 KB Output is correct
23 Correct 37 ms 48132 KB Output is correct
24 Correct 42 ms 47948 KB Output is correct
25 Correct 38 ms 47944 KB Output is correct
26 Correct 37 ms 47952 KB Output is correct
27 Correct 37 ms 47880 KB Output is correct
28 Correct 40 ms 47944 KB Output is correct
29 Correct 41 ms 47404 KB Output is correct
30 Correct 32 ms 47456 KB Output is correct
31 Correct 32 ms 47440 KB Output is correct
32 Correct 37 ms 47328 KB Output is correct
33 Correct 33 ms 47440 KB Output is correct
34 Correct 37 ms 47440 KB Output is correct
35 Correct 885 ms 177316 KB Output is correct
36 Correct 877 ms 177308 KB Output is correct
37 Correct 756 ms 177308 KB Output is correct
38 Correct 770 ms 177332 KB Output is correct
39 Correct 891 ms 177308 KB Output is correct
40 Correct 36 ms 47432 KB Output is correct
41 Correct 34 ms 47432 KB Output is correct
42 Correct 483 ms 175268 KB Output is correct
43 Correct 486 ms 175516 KB Output is correct
44 Correct 476 ms 175516 KB Output is correct
45 Correct 451 ms 177456 KB Output is correct
46 Correct 437 ms 177544 KB Output is correct
47 Correct 505 ms 177504 KB Output is correct
48 Correct 581 ms 177532 KB Output is correct
49 Correct 563 ms 177308 KB Output is correct
50 Correct 571 ms 177264 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct
13 Correct 33 ms 47964 KB Output is correct
14 Correct 32 ms 47432 KB Output is correct
15 Correct 32 ms 47432 KB Output is correct
16 Correct 36 ms 47952 KB Output is correct
17 Correct 34 ms 47884 KB Output is correct
18 Correct 34 ms 48100 KB Output is correct
19 Correct 34 ms 48088 KB Output is correct
20 Correct 37 ms 48140 KB Output is correct
21 Correct 40 ms 47952 KB Output is correct
22 Correct 37 ms 47952 KB Output is correct
23 Correct 37 ms 48132 KB Output is correct
24 Correct 42 ms 47948 KB Output is correct
25 Correct 38 ms 47944 KB Output is correct
26 Correct 37 ms 47952 KB Output is correct
27 Correct 37 ms 47880 KB Output is correct
28 Correct 40 ms 47944 KB Output is correct
29 Correct 41 ms 47404 KB Output is correct
30 Correct 32 ms 47456 KB Output is correct
31 Correct 32 ms 47440 KB Output is correct
32 Correct 37 ms 47328 KB Output is correct
33 Correct 33 ms 47440 KB Output is correct
34 Correct 37 ms 47440 KB Output is correct
35 Correct 94 ms 48216 KB Output is correct
36 Correct 93 ms 48200 KB Output is correct
37 Correct 90 ms 48212 KB Output is correct
38 Correct 91 ms 48200 KB Output is correct
39 Correct 93 ms 48200 KB Output is correct
40 Correct 89 ms 47964 KB Output is correct
41 Correct 80 ms 47944 KB Output is correct
42 Correct 82 ms 47952 KB Output is correct
43 Correct 106 ms 48220 KB Output is correct
44 Correct 110 ms 48200 KB Output is correct
45 Correct 109 ms 48052 KB Output is correct
46 Correct 97 ms 48000 KB Output is correct
47 Correct 97 ms 48204 KB Output is correct
48 Correct 101 ms 48204 KB Output is correct
49 Correct 885 ms 177316 KB Output is correct
50 Correct 877 ms 177308 KB Output is correct
51 Correct 756 ms 177308 KB Output is correct
52 Correct 770 ms 177332 KB Output is correct
53 Correct 891 ms 177308 KB Output is correct
54 Correct 36 ms 47432 KB Output is correct
55 Correct 34 ms 47432 KB Output is correct
56 Correct 483 ms 175268 KB Output is correct
57 Correct 486 ms 175516 KB Output is correct
58 Correct 476 ms 175516 KB Output is correct
59 Correct 451 ms 177456 KB Output is correct
60 Correct 437 ms 177544 KB Output is correct
61 Correct 505 ms 177504 KB Output is correct
62 Correct 581 ms 177532 KB Output is correct
63 Correct 563 ms 177308 KB Output is correct
64 Correct 571 ms 177264 KB Output is correct
65 Correct 1590 ms 192476 KB Output is correct
66 Correct 1754 ms 192748 KB Output is correct
67 Correct 1826 ms 192396 KB Output is correct
68 Correct 1745 ms 192552 KB Output is correct
69 Correct 1634 ms 192380 KB Output is correct
70 Correct 525 ms 175732 KB Output is correct
71 Correct 542 ms 175728 KB Output is correct
72 Correct 565 ms 175516 KB Output is correct
73 Correct 807 ms 192668 KB Output is correct
74 Correct 805 ms 192588 KB Output is correct
75 Correct 821 ms 192700 KB Output is correct
76 Correct 971 ms 192384 KB Output is correct
77 Correct 959 ms 192416 KB Output is correct
78 Correct 995 ms 192300 KB Output is correct

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47440 KB Output is correct
2 Correct 32 ms 47256 KB Output is correct
3 Correct 32 ms 47324 KB Output is correct
4 Correct 39 ms 48104 KB Output is correct
5 Correct 32 ms 47904 KB Output is correct
6 Correct 32 ms 47952 KB Output is correct
7 Correct 35 ms 47748 KB Output is correct
8 Correct 33 ms 47952 KB Output is correct
9 Correct 37 ms 47688 KB Output is correct
10 Correct 33 ms 47724 KB Output is correct
11 Correct 34 ms 47944 KB Output is correct
12 Correct 33 ms 47944 KB Output is correct
13 Correct 33 ms 47964 KB Output is correct
14 Correct 32 ms 47432 KB Output is correct
15 Correct 32 ms 47432 KB Output is correct
16 Correct 36 ms 47952 KB Output is correct
17 Correct 34 ms 47884 KB Output is correct
18 Correct 34 ms 48100 KB Output is correct
19 Correct 34 ms 48088 KB Output is correct
20 Correct 37 ms 48140 KB Output is correct
21 Correct 40 ms 47952 KB Output is correct
22 Correct 37 ms 47952 KB Output is correct
23 Correct 37 ms 48132 KB Output is correct
24 Correct 42 ms 47948 KB Output is correct
25 Correct 38 ms 47944 KB Output is correct
26 Correct 37 ms 47952 KB Output is correct
27 Correct 37 ms 47880 KB Output is correct
28 Correct 40 ms 47944 KB Output is correct
29 Correct 41 ms 47404 KB Output is correct
30 Correct 32 ms 47456 KB Output is correct
31 Correct 32 ms 47440 KB Output is correct
32 Correct 37 ms 47328 KB Output is correct
33 Correct 33 ms 47440 KB Output is correct
34 Correct 37 ms 47440 KB Output is correct
35 Correct 94 ms 48216 KB Output is correct
36 Correct 93 ms 48200 KB Output is correct
37 Correct 90 ms 48212 KB Output is correct
38 Correct 91 ms 48200 KB Output is correct
39 Correct 93 ms 48200 KB Output is correct
40 Correct 89 ms 47964 KB Output is correct
41 Correct 80 ms 47944 KB Output is correct
42 Correct 82 ms 47952 KB Output is correct
43 Correct 106 ms 48220 KB Output is correct
44 Correct 110 ms 48200 KB Output is correct
45 Correct 109 ms 48052 KB Output is correct
46 Correct 97 ms 48000 KB Output is correct
47 Correct 97 ms 48204 KB Output is correct
48 Correct 101 ms 48204 KB Output is correct
49 Runtime error 103 ms 96448 KB Execution killed with signal 11
50 Halted 0 ms 0 KB -