oj.uz

답안 #799344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799344 2023-07-31T13:00:30 Z vjudge1 Candies (JOI18_candies) C++14
100 / 100
 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 ;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 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