Submission #1113313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113313		ntdaccode	Real Mountains (CCO23_day1problem2)	C++17	10 / 25	4723 ms	460228 KiB

Main

#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 (stderr)

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 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 4 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4