Submission #1113228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113228		VinhLuu	Real Mountains (CCO23_day1problem2)	C++17	25 / 25	2262 ms	213552 KiB

Main

#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, m, 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], rrh;
int spe;

int lt(int u,int v){
  if(!v) return 1;
  int x = u;
  int kq = 1;
  while(v){
    if(v & 1) kq = kq * x % mod;
    x = x * x % mod;
    v /= 2;
  }
  return kq;
}

int cal(int l,int r){
  return (l + r) % mod * spe % mod * (r - l + 1) % mod % mod;
}

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;

  spe = lt(2ll, mod - 2);

  for(int i = 1; i <= n; i ++){
    cin >> a[i];
    rrh.push_back(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;
    }
  }
  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
  m = (int)rrh.size();
  for(int i = 1; i <= n; i ++) a[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
  ans = 0;
  des[pos] = lower_bound(all(rrh), max(pf[pos], sf[pos])) - rrh.begin() + 1;
  for(int i = 1; i < pos; i ++) des[i] = lower_bound(all(rrh), pf[i]) - rrh.begin() + 1;
  for(int i = pos + 1; i <= n; i ++) des[i] = lower_bound(all(rrh), sf[i]) - rrh.begin() + 1;

  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 <= m; 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 tmp = rrh[k - 1], nxt = rrh[k];
    int x = (*col.begin());
    int y = (*col.rbegin());
    if(x == y){
      int val = ((get(1, x - 1) + get(x + 1, n)) * (nxt - tmp) % mod + cal(tmp, nxt - 1)) % mod;
      add(ans, val);
    }else{
      int cx = ((get(1, x - 1) + get(x + 1, n)) * (nxt - tmp));
      int cy = ((get(1, y - 1) + get(y + 1, n)) * (nxt - tmp));
//      cerr << cx << " " << cy << " q\n"
      int val = (min(cx + get(y + 1, n) * (nxt - tmp),
                     cy + get(1, x - 1) * (nxt - tmp)) % mod + 3 * cal(tmp, nxt - 1) % mod + (nxt - tmp)) % mod;
//      cerr << val << " " << cx << " " << 2 * cal(tmp, nxt - 1) % mod + (nxt - tmp) << " " << get(y + 1, n) << " r\n";
      add(ans, val);
    }

//    cerr << k << " " << ans << " r\n";

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

    int val = max(0ll, cnt - 2) * (3 * cal(tmp, nxt - 1) % mod + 2 * (nxt - tmp) % mod) % mod;
    add(ans, val);

  }
  cout << ans;
}

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 4 / 4