| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 799344 |
2023-07-31T13:00:30 Z |
vjudge1 |
Candies (JOI18_candies) |
C++14 |
|
658 ms |
44568 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 2e5 ;
ll n, ans, num, a[N + 1], pref[N + 3] ;
set<pair<ll, ll>> s1, s2 ;
set<pair<ll, pair<ll, ll>>> s ;
ll get_sum(ll l, ll r)
{
if(!l || r > n)return -1e18 ;
ll num = 1 ;
if(l % 2 == 0)num = -1 ;
return (pref[r] - pref[l - 1]) * num ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n ;
for(ll i = 1 ; i <= n ; i++)
{
cin >> a[i] ;
s1.insert({i, i}) ;
s2.insert({-i, -i}) ;
pref[i] = pref[i - 1] ;
if(i % 2)pref[i] += a[i] ;
else pref[i] -= a[i] ;
s.insert({a[i], {i, i}}) ;
}
pref[n + 1] = pref[n] ;
for(ll i = 1 ; i <= (n + 1) / 2 ; i++)
{
ll num = (*s.rbegin()).fi, l = (*s.rbegin()).se.fi, r = (*s.rbegin()).se.se ;
pair<ll, ll> pz1 = {l, r + 1}, pz2 = {-r, -l + 1} ;
s.erase(*s.rbegin()) ;
s1.erase({l, r}) ;
s2.erase({-r, -l}) ;
if(s1.lower_bound({l, r}) != s1.end())
{
pz1 = *s1.lower_bound({l, r}) ;
s1.erase(pz1) ;
s2.erase({-pz1.se, -pz1.fi}) ;
s.erase({get_sum(pz1.fi, pz1.se), {pz1.fi, pz1.se}}) ;
}
if(s2.lower_bound({-r, -l}) != s2.end())
{
pz2 = *s2.lower_bound({-r, -l}) ;
s1.erase({-pz2.se, -pz2.fi}) ;
s2.erase(pz2) ;
s.erase({get_sum(-pz2.se, -pz2.fi), {-pz2.se, -pz2.fi}}) ;
}
l = -pz2.se ;
r = pz1.se ;
s1.insert({l, r}) ;
s2.insert({-r, -l}) ;
s.insert({get_sum(l, r), {l, r}}) ;
ans += num ;
// cout<<num<<' '<<l<<' '<<r << ' ' << pz1.fi<<' '<<pz1.se << ' '<<-pz2.se <<' '<<-pz2.fi<<'\n' ;
cout << ans << '\n' ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
724 KB |
Output is correct |
| 3 |
Correct |
3 ms |
776 KB |
Output is correct |
| 4 |
Correct |
3 ms |
724 KB |
Output is correct |
| 5 |
Correct |
3 ms |
724 KB |
Output is correct |
| 6 |
Correct |
3 ms |
780 KB |
Output is correct |
| 7 |
Correct |
3 ms |
728 KB |
Output is correct |
| 8 |
Correct |
3 ms |
724 KB |
Output is correct |
| 9 |
Correct |
2 ms |
728 KB |
Output is correct |
| 10 |
Correct |
2 ms |
724 KB |
Output is correct |
| 11 |
Correct |
3 ms |
724 KB |
Output is correct |
| 12 |
Correct |
3 ms |
724 KB |
Output is correct |
| 13 |
Correct |
3 ms |
724 KB |
Output is correct |
| 14 |
Correct |
3 ms |
724 KB |
Output is correct |
| 15 |
Correct |
3 ms |
724 KB |
Output is correct |
| 16 |
Correct |
3 ms |
724 KB |
Output is correct |
| 17 |
Correct |
3 ms |
724 KB |
Output is correct |
| 18 |
Correct |
3 ms |
724 KB |
Output is correct |
| 19 |
Correct |
2 ms |
724 KB |
Output is correct |
| 20 |
Correct |
2 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
724 KB |
Output is correct |
| 3 |
Correct |
3 ms |
776 KB |
Output is correct |
| 4 |
Correct |
3 ms |
724 KB |
Output is correct |
| 5 |
Correct |
3 ms |
724 KB |
Output is correct |
| 6 |
Correct |
3 ms |
780 KB |
Output is correct |
| 7 |
Correct |
3 ms |
728 KB |
Output is correct |
| 8 |
Correct |
3 ms |
724 KB |
Output is correct |
| 9 |
Correct |
2 ms |
728 KB |
Output is correct |
| 10 |
Correct |
2 ms |
724 KB |
Output is correct |
| 11 |
Correct |
3 ms |
724 KB |
Output is correct |
| 12 |
Correct |
3 ms |
724 KB |
Output is correct |
| 13 |
Correct |
3 ms |
724 KB |
Output is correct |
| 14 |
Correct |
3 ms |
724 KB |
Output is correct |
| 15 |
Correct |
3 ms |
724 KB |
Output is correct |
| 16 |
Correct |
3 ms |
724 KB |
Output is correct |
| 17 |
Correct |
3 ms |
724 KB |
Output is correct |
| 18 |
Correct |
3 ms |
724 KB |
Output is correct |
| 19 |
Correct |
2 ms |
724 KB |
Output is correct |
| 20 |
Correct |
2 ms |
724 KB |
Output is correct |
| 21 |
Correct |
655 ms |
44408 KB |
Output is correct |
| 22 |
Correct |
650 ms |
44360 KB |
Output is correct |
| 23 |
Correct |
658 ms |
44368 KB |
Output is correct |
| 24 |
Correct |
309 ms |
44320 KB |
Output is correct |
| 25 |
Correct |
300 ms |
44324 KB |
Output is correct |
| 26 |
Correct |
288 ms |
44236 KB |
Output is correct |
| 27 |
Correct |
317 ms |
44444 KB |
Output is correct |
| 28 |
Correct |
316 ms |
44456 KB |
Output is correct |
| 29 |
Correct |
329 ms |
44436 KB |
Output is correct |
| 30 |
Correct |
326 ms |
44416 KB |
Output is correct |
| 31 |
Correct |
328 ms |
44384 KB |
Output is correct |
| 32 |
Correct |
332 ms |
44424 KB |
Output is correct |
| 33 |
Correct |
444 ms |
44272 KB |
Output is correct |
| 34 |
Correct |
444 ms |
44188 KB |
Output is correct |
| 35 |
Correct |
449 ms |
44236 KB |
Output is correct |
| 36 |
Correct |
656 ms |
44416 KB |
Output is correct |
| 37 |
Correct |
654 ms |
44328 KB |
Output is correct |
| 38 |
Correct |
651 ms |
44364 KB |
Output is correct |
| 39 |
Correct |
295 ms |
44300 KB |
Output is correct |
| 40 |
Correct |
291 ms |
44220 KB |
Output is correct |
| 41 |
Correct |
299 ms |
44200 KB |
Output is correct |
| 42 |
Correct |
310 ms |
44440 KB |
Output is correct |
| 43 |
Correct |
314 ms |
44568 KB |
Output is correct |
| 44 |
Correct |
310 ms |
44448 KB |
Output is correct |
| 45 |
Correct |
335 ms |
44364 KB |
Output is correct |
| 46 |
Correct |
330 ms |
44456 KB |
Output is correct |
| 47 |
Correct |
329 ms |
44368 KB |
Output is correct |
| 48 |
Correct |
441 ms |
44124 KB |
Output is correct |
| 49 |
Correct |
451 ms |
44324 KB |
Output is correct |
| 50 |
Correct |
442 ms |
44148 KB |
Output is correct |
