oj.uz

Submission #1113313

# Submission time Handle Problem Language Result Execution time Memory
1113313 2024-11-16T11:05:50 Z ntdaccode Real Mountains (CCO23_day1problem2) C++17
10 / 25
 4723 ms 460228 KB 
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i = a;i <= b; i++)
#define int long long
#define pb push_back
using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 5e3 + 10;
const int mod = 1e6 + 3;

int n,h[M];
int target[M];
vector<int> Q[M];
vector<int> rrh;

int calc(int l,int r) {
  int x = l + r;
  int y = r - l + 1;
  if(x % 2 == 0) {
    x /= 2;
    x %= mod;
    y %= mod;
    return (x * y) % mod;
  }
  y /= 2;
  x %= mod;
  y %= mod;
  return (x * y) % mod;
}
int len(int i) {
  int x = rrh[i + 1] % mod;
  int y = rrh[i] % mod;
  return (x - y + mod ) % mod;
}
int add(int a,int b) {
  a %= mod;
  b %= mod;
  return (a + b) % mod;
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  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 >> h[i];

  int suf = 0,pre = 0;
  for(int i = 1;i <= n; i++) {
    pre = max(pre, h[i]);
    target[i] =  pre ;
  }
  for(int i = n; i != 0; i--) {
    suf = max(suf, h[i]);
    target[i] = min(target[i], suf);
  }

  for(int i = 1;i <= n; i++) rrh.pb(h[i]);
  sort(rrh.begin(),rrh.end());
  rrh.resize(unique (rrh.begin(), rrh.end()) - rrh.begin());
  for(int i = 1;i <= n; i++) {
      h[i] = lower_bound(rrh.begin(),rrh.end(),h[i]) - rrh.begin() ;
      target[i] = lower_bound(rrh.begin(),rrh.end(),target[i]) - rrh.begin() ;
      //cout << h[i] << " " << target[i] << "\n";
  }

  for(int i = 1;i <= n; i++) {
    if(h[i] != target[i]) {
      Q[h[i]].pb(i);
    }
  }
  int kq = 0;
  int m = rrh.size();
  for(int high = 0;high <= m - 2; high++) {
    if(Q[high].size() == 0) continue;
    if(Q[high].size() == 1) {

      int x = 1e9 , y = 1e9 , cur = Q[high][0];
      for(int j = 1; j < cur; j++) {
        if(h[j] > h[cur]) x = min(x,rrh[h[j]]);
      }
      for(int j = cur + 1; j <= n ;j++) {
        if(h[j] > h[cur]) y = min(y,rrh[h[j]]);
      }
      kq = ( (kq + len(high) * add(x,y) % mod) % mod + calc(rrh[high],rrh[high + 1] - 1) ) % mod;
      h[cur]++;
      if(h[cur] != target[cur]) Q[h[cur]].pb(cur);


    }
    else {
      sort(Q[high].begin(),Q[high].end());
      int pre_l = 1e9 , pre_r = 1e9 , suf_l = 1e9 , suf_r = 1e9;
      int l = Q[high][0], r = Q[high].back();
      for(int j = 1;j < l ; j++) {
        if(h[j] > h[l]) pre_l = min(pre_l,rrh[h[j]]);
      }
      for(int j = l + 1;j <= n; j++) {
        if(h[j] > h[l]) suf_l = min(suf_l,rrh[h[j]]);
      }
      for(int j = 1; j < r; j++) {
        if(h[j] > h[r]) pre_r = min(pre_r,rrh[h[j]]);
      }
      for(int j = r + 1;j <= n; j++) {
        if(h[j] > h[r]) suf_r = min(suf_r,rrh[h[j]]);
      }

//      cout << Q[high].size() << " " << pre_l << " " << suf_l << " " << pre_r << " " << suf_r << "\n";
//      cout << rrh[high] << " " << rrh[high + 1] << " ";
//      cout << calc(rrh[high],rrh[high + 1] - 1) << " ";
//      cout << calc(rrh[high] + 1,rrh[high + 1]) << "\n";

      pre_l %= mod;
      pre_r %= mod;
      suf_l %= mod;
      suf_r %= mod;
      int x = ( ( (len(high) * add(pre_l,suf_l) % mod + 2ll * calc(rrh[high],rrh[high + 1] - 1ll) % mod) % mod +
                calc(rrh[high] + 1ll,rrh[high + 1]) ) % mod + (rrh[high + 1] - rrh[high]) * suf_r % mod ) % mod;
      int y = ( ( (len(high) * add(pre_r,suf_r) % mod + 2ll * calc(rrh[high],rrh[high + 1] - 1ll) % mod) % mod +
                calc(rrh[high] + 1ll,rrh[high + 1]) ) % mod + (rrh[high + 1] - rrh[high]) * pre_l % mod ) % mod;

      kq = (kq + min(x,y)) % mod;
      //cout << kq << " ";
      int sz = Q[high].size();
      kq = (kq + ( (sz - 2ll) * ( ( calc(rrh[high],rrh[high + 1] - 1ll) + 2ll * calc(rrh[high] + 1ll ,rrh[high+1]) % mod ) % mod) % mod) % mod ) % mod;
      for(int idx : Q[high]) {
          h[idx]++;
          if(h[idx] != target[idx]) Q[h[idx]].pb(idx);
      }
    }
  }

  cout << kq % mod;
}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct
13 Correct 35 ms 26448 KB Output is correct
14 Correct 16 ms 23720 KB Output is correct
15 Correct 16 ms 23888 KB Output is correct
16 Correct 35 ms 26440 KB Output is correct
17 Correct 33 ms 26192 KB Output is correct
18 Correct 30 ms 26156 KB Output is correct
19 Correct 40 ms 26188 KB Output is correct
20 Correct 20 ms 24316 KB Output is correct
21 Correct 17 ms 24260 KB Output is correct
22 Correct 20 ms 24336 KB Output is correct
23 Correct 29 ms 26448 KB Output is correct
24 Correct 30 ms 26412 KB Output is correct
25 Correct 27 ms 26428 KB Output is correct
26 Correct 26 ms 26192 KB Output is correct
27 Correct 26 ms 26192 KB Output is correct
28 Correct 26 ms 26192 KB Output is correct
29 Correct 16 ms 23888 KB Output is correct
30 Correct 16 ms 23888 KB Output is correct
31 Correct 16 ms 23888 KB Output is correct
32 Correct 16 ms 23888 KB Output is correct
33 Correct 16 ms 23888 KB Output is correct
34 Correct 16 ms 23888 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct
13 Correct 35 ms 26448 KB Output is correct
14 Correct 16 ms 23720 KB Output is correct
15 Correct 16 ms 23888 KB Output is correct
16 Correct 35 ms 26440 KB Output is correct
17 Correct 33 ms 26192 KB Output is correct
18 Correct 30 ms 26156 KB Output is correct
19 Correct 40 ms 26188 KB Output is correct
20 Correct 20 ms 24316 KB Output is correct
21 Correct 17 ms 24260 KB Output is correct
22 Correct 20 ms 24336 KB Output is correct
23 Correct 29 ms 26448 KB Output is correct
24 Correct 30 ms 26412 KB Output is correct
25 Correct 27 ms 26428 KB Output is correct
26 Correct 26 ms 26192 KB Output is correct
27 Correct 26 ms 26192 KB Output is correct
28 Correct 26 ms 26192 KB Output is correct
29 Correct 16 ms 23888 KB Output is correct
30 Correct 16 ms 23888 KB Output is correct
31 Correct 16 ms 23888 KB Output is correct
32 Correct 16 ms 23888 KB Output is correct
33 Correct 16 ms 23888 KB Output is correct
34 Correct 16 ms 23888 KB Output is correct
35 Correct 324 ms 135836 KB Output is correct
36 Incorrect 295 ms 136008 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct
13 Correct 35 ms 26448 KB Output is correct
14 Correct 16 ms 23720 KB Output is correct
15 Correct 16 ms 23888 KB Output is correct
16 Correct 35 ms 26440 KB Output is correct
17 Correct 33 ms 26192 KB Output is correct
18 Correct 30 ms 26156 KB Output is correct
19 Correct 40 ms 26188 KB Output is correct
20 Correct 20 ms 24316 KB Output is correct
21 Correct 17 ms 24260 KB Output is correct
22 Correct 20 ms 24336 KB Output is correct
23 Correct 29 ms 26448 KB Output is correct
24 Correct 30 ms 26412 KB Output is correct
25 Correct 27 ms 26428 KB Output is correct
26 Correct 26 ms 26192 KB Output is correct
27 Correct 26 ms 26192 KB Output is correct
28 Correct 26 ms 26192 KB Output is correct
29 Correct 16 ms 23888 KB Output is correct
30 Correct 16 ms 23888 KB Output is correct
31 Correct 16 ms 23888 KB Output is correct
32 Correct 16 ms 23888 KB Output is correct
33 Correct 16 ms 23888 KB Output is correct
34 Correct 16 ms 23888 KB Output is correct
35 Correct 324 ms 135836 KB Output is correct
36 Incorrect 295 ms 136008 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct
13 Correct 35 ms 26448 KB Output is correct
14 Correct 16 ms 23720 KB Output is correct
15 Correct 16 ms 23888 KB Output is correct
16 Correct 35 ms 26440 KB Output is correct
17 Correct 33 ms 26192 KB Output is correct
18 Correct 30 ms 26156 KB Output is correct
19 Correct 40 ms 26188 KB Output is correct
20 Correct 20 ms 24316 KB Output is correct
21 Correct 17 ms 24260 KB Output is correct
22 Correct 20 ms 24336 KB Output is correct
23 Correct 29 ms 26448 KB Output is correct
24 Correct 30 ms 26412 KB Output is correct
25 Correct 27 ms 26428 KB Output is correct
26 Correct 26 ms 26192 KB Output is correct
27 Correct 26 ms 26192 KB Output is correct
28 Correct 26 ms 26192 KB Output is correct
29 Correct 16 ms 23888 KB Output is correct
30 Correct 16 ms 23888 KB Output is correct
31 Correct 16 ms 23888 KB Output is correct
32 Correct 16 ms 23888 KB Output is correct
33 Correct 16 ms 23888 KB Output is correct
34 Correct 16 ms 23888 KB Output is correct
35 Correct 4723 ms 459524 KB Output is correct
36 Correct 4688 ms 460228 KB Output is correct
37 Correct 4616 ms 457196 KB Output is correct
38 Correct 4587 ms 457184 KB Output is correct
39 Correct 4594 ms 459848 KB Output is correct
40 Correct 24 ms 24144 KB Output is correct
41 Correct 18 ms 24148 KB Output is correct
42 Correct 601 ms 110004 KB Output is correct
43 Correct 603 ms 107948 KB Output is correct
44 Correct 617 ms 108964 KB Output is correct
45 Correct 2691 ms 455820 KB Output is correct
46 Correct 2700 ms 458588 KB Output is correct
47 Correct 2615 ms 456240 KB Output is correct
48 Correct 4293 ms 451492 KB Output is correct
49 Correct 4173 ms 455488 KB Output is correct
50 Correct 4296 ms 451676 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct
13 Correct 35 ms 26448 KB Output is correct
14 Correct 16 ms 23720 KB Output is correct
15 Correct 16 ms 23888 KB Output is correct
16 Correct 35 ms 26440 KB Output is correct
17 Correct 33 ms 26192 KB Output is correct
18 Correct 30 ms 26156 KB Output is correct
19 Correct 40 ms 26188 KB Output is correct
20 Correct 20 ms 24316 KB Output is correct
21 Correct 17 ms 24260 KB Output is correct
22 Correct 20 ms 24336 KB Output is correct
23 Correct 29 ms 26448 KB Output is correct
24 Correct 30 ms 26412 KB Output is correct
25 Correct 27 ms 26428 KB Output is correct
26 Correct 26 ms 26192 KB Output is correct
27 Correct 26 ms 26192 KB Output is correct
28 Correct 26 ms 26192 KB Output is correct
29 Correct 16 ms 23888 KB Output is correct
30 Correct 16 ms 23888 KB Output is correct
31 Correct 16 ms 23888 KB Output is correct
32 Correct 16 ms 23888 KB Output is correct
33 Correct 16 ms 23888 KB Output is correct
34 Correct 16 ms 23888 KB Output is correct
35 Correct 324 ms 135836 KB Output is correct
36 Incorrect 295 ms 136008 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 17 ms 23888 KB Output is correct
3 Correct 18 ms 23888 KB Output is correct
4 Correct 28 ms 26444 KB Output is correct
5 Correct 18 ms 24144 KB Output is correct
6 Correct 16 ms 24144 KB Output is correct
7 Correct 17 ms 24144 KB Output is correct
8 Correct 17 ms 24144 KB Output is correct
9 Correct 22 ms 23968 KB Output is correct
10 Correct 22 ms 24088 KB Output is correct
11 Correct 35 ms 26448 KB Output is correct
12 Correct 25 ms 26448 KB Output is correct
13 Correct 35 ms 26448 KB Output is correct
14 Correct 16 ms 23720 KB Output is correct
15 Correct 16 ms 23888 KB Output is correct
16 Correct 35 ms 26440 KB Output is correct
17 Correct 33 ms 26192 KB Output is correct
18 Correct 30 ms 26156 KB Output is correct
19 Correct 40 ms 26188 KB Output is correct
20 Correct 20 ms 24316 KB Output is correct
21 Correct 17 ms 24260 KB Output is correct
22 Correct 20 ms 24336 KB Output is correct
23 Correct 29 ms 26448 KB Output is correct
24 Correct 30 ms 26412 KB Output is correct
25 Correct 27 ms 26428 KB Output is correct
26 Correct 26 ms 26192 KB Output is correct
27 Correct 26 ms 26192 KB Output is correct
28 Correct 26 ms 26192 KB Output is correct
29 Correct 16 ms 23888 KB Output is correct
30 Correct 16 ms 23888 KB Output is correct
31 Correct 16 ms 23888 KB Output is correct
32 Correct 16 ms 23888 KB Output is correct
33 Correct 16 ms 23888 KB Output is correct
34 Correct 16 ms 23888 KB Output is correct
35 Correct 324 ms 135836 KB Output is correct
36 Incorrect 295 ms 136008 KB Output isn't correct
37 Halted 0 ms 0 KB -