oj.uz

Submission #487985

# Submission time Handle Problem Language Result Execution time Memory
487985 2021-11-17T10:57:03 Z David_M Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 48488 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){

        for (ll i=0; i<=n; i++){
            pair<pii,pii> y=getmaxmin(i, i);
        }

        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:84:27: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   84 |             pair<pii,pii> y=getmaxmin(i, i);
      |                           ^
candies.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 30 ms 716 KB Output is correct
4 Correct 259 ms 680 KB Output is correct
5 Execution timed out 5091 ms 844 KB Time limit exceeded

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5065 ms 47092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Execution timed out 5070 ms 38584 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Execution timed out 5078 ms 48488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 30 ms 716 KB Output is correct
4 Correct 259 ms 680 KB Output is correct
5 Execution timed out 5091 ms 844 KB Time limit exceeded