oj.uz

Submission #1112876

# Submission time Handle Problem Language Result Execution time Memory
1112876 2024-11-15T07:00:04 Z zNatsumi Real Mountains (CCO23_day1problem2) C++17
0 / 25
 1 ms 2552 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

const int N = 1e6 + 5,
          mod = 1e6 + 3;

int n, a[N];
bool DKL[N], DKR[N];

namespace sub1{
  priority_queue<ii, vector<ii>, greater<>> pq;

  void solve(){
    for(int i = 1; i <= n; i++) pq.push({a[i], i});

    int res = 0;
    while(pq.size()){
      auto idx = pq.top().second; pq.pop();

      int posL = -1, posR = -1;
      {
        int l = 1, r = idx - 1;
        while(l <= r){
          int mid = l + r >> 1;
          if(a[mid] > a[idx]) l = (posL = mid) + 1;
          else r = mid - 1;
        }
      }
      {
        int l = idx + 1, r = n;
        while(l <= r){
          int mid = l + r >> 1;
          if(a[mid] > a[idx]) r = (posR = mid) - 1;
          else l = mid + 1;
        }
      }
      if(posL == -1 && posR == -1) break;
      else if(posL == -1 || posR == -1) continue;

      res = (res + a[posL] + a[idx] + a[posR]) % mod;

      a[idx]++;
      pq.push({a[idx], idx});
    }
    cout << res << "\n";
  }
}

namespace sub2{
  priority_queue<ii, vector<ii>, greater<>> pq;

  void solve(){
    for(int i = 1; i <= n; i++) pq.push({a[i], i});

    int res = 0;
    while(pq.size()){
      auto idx = pq.top().second; pq.pop();

      int posL = -1, posR = -1;

      for(int i = 1; i <= idx - 1; i++)
        if(a[i] > a[idx] && (posL == -1 || a[i] < a[posL])) posL = i;

      for(int i = idx + 1; i <= n; i++)
        if(a[i] > a[idx] && (posR == -1 || a[i] < a[posR])) posR = i;

      if(posL == -1 && posR == -1) break;
      else if(posL == -1 || posR == -1) continue;

      res = (res + a[posL] + a[idx] + a[posR]) % mod;

      a[idx]++;
      pq.push({a[idx], idx});
    }
    cout << res << "\n";
  }
}

namespace sub2_5{
  priority_queue<ii, vector<ii>, greater<>> pq;
  set<int> s[105];

  void solve(){
    for(int i = 1; i <= n; i++){
      pq.push({a[i], i});
      s[a[i]].insert(i);
    }
    int res = 0;
    while(pq.size()){
      auto idx = pq.top().second; pq.pop();

      int posL = -1, posR = -1;

      for(int i = a[idx] + 1; i <= 100; i++) if(s[i].size()){
        if(posL == -1 && *s[i].begin() < idx) posL = *s[i].begin();
        if(posR == -1 && *s[i].rbegin() > idx) posR = *s[i].rbegin();
      }

      if(posL == -1 && posR == -1) break;
      else if(posL == -1 || posR == -1) continue;

      res = (res + a[posL] + a[idx] + a[posR]) % mod;

      s[a[idx]].erase(idx);
      a[idx]++;
      s[a[idx]].insert(idx);
      pq.push({a[idx], idx});
    }
    cout << res << "\n";
  }
}


int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  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];
  DKL[1] = DKR[n] = true;
  for(int i = 2; i <= n; i++)
    if(a[i - 1] >= a[i]) DKL[i] = true;
    else break;
  for(int i = n - 1; i >= 1; i--)
    if(a[i + 1] >= a[i]) DKR[i] = true;
    else break;
  bool ok = false;
  for(int i = 1; i <= n; i++) ok |= (DKL[i] & DKR[i]);

  if(ok) sub1::solve();
  else if(n <= 1000) sub2::solve();
  else sub2_5::solve();

  return 0;
}

Compilation message

Main.cpp: In function 'void sub1::solve()':
Main.cpp:27:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |           int mid = l + r >> 1;
      |                     ~~^~~
Main.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |           int mid = l + r >> 1;
      |                     ~~^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -