This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]);
sub2_5::solve();
return 0;
}
Compilation message (stderr)
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;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |