Submission #1113217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113217		VinhLuu	Real Mountains (CCO23_day1problem2)	C++17	0 / 25	38 ms	47440 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, 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);
  }

  int cnt = 0;
  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());
    int val = get(1, x - 1) + get(x + 1, n) + k;
    add(ans, val);
    if(x != y){
      val = get(1, y - 1) + get(y + 1, n) + k;
      add(ans, val);
    }
    val = max(0ll, y - x - 1) * (3 * k % mod + 2) % mod;
    add(ans, val);
  }
  cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:7: warning: unused variable 'cnt' [-Wunused-variable]
   82 |   int cnt = 0;
      |       ^~~
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: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4