oj.uz

Submission #487988

# Submission time Handle Problem Language Result Execution time Memory
487988 2021-11-17T11:02:33 Z David_M Distributing Candies (IOI21_candies) C++17
100 / 100
 1840 ms 60348 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define vi vector<ll>
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pii pair<ll, ll>
#define vpii vector<pii>
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e18 + 7;
ll n, m, lazy[8*N];

pair<pii,pii> T[8*N], o={{-INF, -1}, {INF, -1}};


void push(ll x){
    lazy[x<<1  ]+=lazy[x];
    lazy[x<<1|1]+=lazy[x];
    T[x].F.F+=lazy[x];
    T[x].S.F+=lazy[x];
    lazy[x]=0;
}

void build(ll L=0, ll R=n, ll x=1){
    if(L==R){
        T[x]={{0, L}, {0, L}};
        return;
    }
    ll m=L+R>>1;
    build(L, m, x<<1);
    build(m+1, R, x<<1|1);
    auto xl=T[x<<1], xr=T[x<<1|1];
    T[x]={max(xl.F, xr.F), min(xl.S, xr.S)};
}

void upd(ll l, ll r, ll val, ll L=0, ll R=n, ll x=1){
    if(R<l || L>r)return;
    if(L>=l && R<=r){
        lazy[x]+=val;
        return;
    }
    ll m=L+R>>1;
    push(x);
    upd(l, r, val, L, m, x<<1);
    upd(l, r, val, m+1, R, x<<1|1);

    push(x<<1); push(x<<1|1);
    auto xl=T[x<<1], xr=T[x<<1|1];
    T[x]={max(xl.F, xr.F), min(xl.S, xr.S)};
}

pair<pii,pii> getmaxmin(ll l, ll r, ll L=0, ll R=n, ll x=1){
    if(R<l || L>r)return o;
    push(x);
    if(L>=l && R<=r){
        return T[x];
    }
    ll m=L+R>>1;
    auto [mx1, mn1] = getmaxmin(l, r, L, m, x<<1);
    auto [mx2, mn2] = getmaxmin(l, r, m+1, R, x<<1|1);
    return {max(mx1, mx2), min(mn1, mn2)};
}

ll get(ll i, ll L=0, ll R=n, ll x=1){
    push(x);
    if(L==R)return T[x].F.F;
    ll m=L+R>>1;
    if(m>=i){
        return get(i, L, m, x<<1);
    }else{
        return get(i, m+1, R, x<<1|1);
    }
}

ll solve(ll c){
    ll l=0, r=n, d=0, u=-1, dval, uval, g=0;

    while(l<=r){

        ll m=l+r>>1;
        auto [mx,mn] = getmaxmin(m, n);
        if(mx.F-mn.F<c)r=m-1;
        else{
            g=1;
            dval=mn.F; d=mn.S;
            uval=mx.F; u=mx.S;
            l=m+1;
        }
    }
    if(!g)return get(n)-getmaxmin(0,n).S.F;
    if(d<u){
        return c-(get(u)-get(n));
    }else{
        return get(n)-get(d);
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    m = sz(c), n=sz(l);
    vector<int> ans(m);
    vpii a[m+1];
    build();
    for (ll i=0; i<n; i++){
        a[l[i]  ].pb({v[i],i});
        a[r[i]+1].pb({v[i],i});
    }
    set<pii> s;
    for (ll i=0; i<m; i++){

        for (auto [val,t]:a[i]){
            if(s.find({val,t})!=s.end()){
                s.erase({val,t});
                upd(t+1, n, -val);
            }else{
                s.insert({val,t});
                upd(t+1, n, val);
            }
        }
        ans[i]=solve(c[i]);
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void build(long long int, long long int, long long int)':
candies.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     ll m=L+R>>1;
      |          ~^~
candies.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
candies.cpp:45:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     ll m=L+R>>1;
      |          ~^~
candies.cpp: In function 'std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > getmaxmin(long long int, long long int, long long int, long long int, long long int)':
candies.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     ll m=L+R>>1;
      |          ~^~
candies.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
candies.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     ll m=L+R>>1;
      |          ~^~
candies.cpp: In function 'long long int solve(long long int)':
candies.cpp:83:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |         ll m=l+r>>1;
      |              ~^~
candies.cpp:79:29: warning: variable 'dval' set but not used [-Wunused-but-set-variable]
   79 |     ll l=0, r=n, d=0, u=-1, dval, uval, g=0;
      |                             ^~~~
candies.cpp:79:35: warning: variable 'uval' set but not used [-Wunused-but-set-variable]
   79 |     ll l=0, r=n, d=0, u=-1, dval, uval, g=0;
      |                                   ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 9 ms 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 53376 KB Output is correct
2 Correct 1679 ms 57404 KB Output is correct
3 Correct 1785 ms 57276 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 605 ms 44060 KB Output is correct
3 Correct 449 ms 11048 KB Output is correct
4 Correct 1840 ms 59300 KB Output is correct
5 Correct 1677 ms 59776 KB Output is correct
6 Correct 1476 ms 60072 KB Output is correct
7 Correct 1440 ms 59672 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 296 ms 48544 KB Output is correct
4 Correct 342 ms 9112 KB Output is correct
5 Correct 1196 ms 59048 KB Output is correct
6 Correct 1125 ms 59688 KB Output is correct
7 Correct 1026 ms 60348 KB Output is correct
8 Correct 1177 ms 58812 KB Output is correct
9 Correct 1319 ms 60288 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 9 ms 776 KB Output is correct
6 Correct 1570 ms 53376 KB Output is correct
7 Correct 1679 ms 57404 KB Output is correct
8 Correct 1785 ms 57276 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 605 ms 44060 KB Output is correct
11 Correct 449 ms 11048 KB Output is correct
12 Correct 1840 ms 59300 KB Output is correct
13 Correct 1677 ms 59776 KB Output is correct
14 Correct 1476 ms 60072 KB Output is correct
15 Correct 1440 ms 59672 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 296 ms 48544 KB Output is correct
19 Correct 342 ms 9112 KB Output is correct
20 Correct 1196 ms 59048 KB Output is correct
21 Correct 1125 ms 59688 KB Output is correct
22 Correct 1026 ms 60348 KB Output is correct
23 Correct 1177 ms 58812 KB Output is correct
24 Correct 1319 ms 60288 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 370 ms 9088 KB Output is correct
27 Correct 664 ms 46692 KB Output is correct
28 Correct 1704 ms 57908 KB Output is correct
29 Correct 1612 ms 58296 KB Output is correct
30 Correct 1555 ms 58508 KB Output is correct
31 Correct 1469 ms 58720 KB Output is correct
32 Correct 1441 ms 59004 KB Output is correct