/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n;
ll a[N], T[N], lazy[N];
void build(int x){
for(int i =0; i <= 4*x; ++i) T[i] = lazy[i] = 0;
}
void push(int k){
T[k<<1] += lazy[k];
T[k<<1|1] += lazy[k];
lazy[k<<1] += lazy[k];
lazy[k<<1|1] += lazy[k];
lazy[k] = 0;
}
void upd(int l, int r, int ql, int qr, int k, ll val){
if(ql>r||l>qr) return;
if(ql <= l && r <= qr){
lazy[k] += val;
T[k] += val;
return;
}
push(k);
int m = l+r>>1;
upd(l, m, ql, qr, k<<1, val);
upd(m+1, r, ql, qr, k<<1|1, val);
T[k] = max(T[k<<1], T[k<<1|1]);
// cout << l << ' ' << r << ' ' << T[k] << '\n';
}
void upd2(int l, int r, int ql, int qr, int k, ll val){
if(ql>r||l>qr) return;
if(ql <= l && r <= qr){
T[k] = val;
return;
}
push(k);
int m = l+r>>1;
upd2(l, m, ql, qr, k<<1, val);
upd2(m+1, r, ql, qr, k<<1|1, val);
T[k] = max(T[k<<1], T[k<<1|1]);
// cout << l << ' ' << r << ' ' << T[k] << '\n';
}
ll get(int l, int r, int p, int k){
if(l > r || l > p || r < p) return 0;
if(l == r){
return T[k];
}
push(k);
int m = l+r>>1;
if(p <= m) return get(l, m, p, k<<1);
return get(m+1, r, p, k<<1|1);
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
build(n);
vector<pair<ll, ll>> A;
for(int i = 1; i <= n; ++i){
A.pb({a[i], i});
}
sort(all(A), greater<pair<ll, ll>>());
for(int i = 0; i + 1 < n; i += 2){
int x = A[i].ss;
int y = A[i+1].ss;
if(x > y) swap(x, y);
if(a[x] >= a[y]){
upd(1, n, x + 2, n, 1, a[x]);
upd2(1, n, x, x, 1, get(1, n, x - 2, 1) + a[x]);
}else{
upd(1, n, y + 2, n, 1, a[y] - a[x]);
upd(1, n, x + 2, n, 1, a[x]);
upd2(1, n, x, x, 1, get(1, n, x - 2, 1) + a[x]);
upd2(1, n, y, y, 1, get(1, n, y - 2, 1) + a[y]);
}
cout << T[1];
cout << '\n';
}
if(n % 2){
ll x = 0, y = 0;
for(int i = 1; i <= n; i += 2) x += a[i];
cout << x;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
candies.cpp: In function 'void upd(int, int, int, int, int, long long int)':
candies.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = l+r>>1;
| ~^~
candies.cpp: In function 'void upd2(int, int, int, int, int, long long int)':
candies.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int m = l+r>>1;
| ~^~
candies.cpp: In function 'long long int get(int, int, int, int)':
candies.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int m = l+r>>1;
| ~^~
candies.cpp: In function 'void solve()':
candies.cpp:91:15: warning: unused variable 'y' [-Wunused-variable]
91 | ll x = 0, y = 0;
| ^
candies.cpp: In function 'int main()':
candies.cpp:100:15: warning: unused variable 'aa' [-Wunused-variable]
100 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
