oj.uz

Submission #435030

# Submission time Handle Problem Language Result Execution time Memory
435030 2021-06-22T20:34:07 Z Enkognit Distributing Candies (IOI21_candies) C++17
29 / 100
 2068 ms 54068 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second

ll n, m, q;

pll d[1000001];
ll tt[1000001];

void build(int h,int l,int r)
{
    if (l==r)
    {
        d[h]=mp(0, 0);
        return;
    }
    int w=(l+r)/2;
    build(h*2,l,w);
    build(h*2+1,w+1,r);
    d[h]=mp(0, 0);
}

void push(int h)
{
    if (tt[h])
    {
        d[h*2].fi+=tt[h];
        d[h*2].se+=tt[h];
        d[h*2+1].fi+=tt[h];
        d[h*2+1].se+=tt[h];
        tt[h*2]+=tt[h];
        tt[h*2+1]+=tt[h];
        tt[h]=0;
    }
}

void update(int h,int l,int r,int x,int y,int k)
{
    if (x>y) return;
    if (l==x && y==r)
    {
        d[h].fi+=k;
        d[h].se+=k;
        tt[h]+=k;
        return;
    }
    push(h);
    int w=(l+r)/2;
    update(h*2,l,w,x,min(y,w),k);
    update(h*2+1,w+1,r,max(x,w+1),y,k);
    d[h].fi=min(d[h*2].fi,d[h*2+1].fi);
    d[h].se=max(d[h*2].se,d[h*2+1].se);
}

ll get_min(int h,int l,int r,int x,int y)
{
    if (x>y) return 1e18;
    if (l==x && y==r) return d[h].fi;
    int w=(l+r)/2;
    push(h);
    return min(get_min(h*2,l,w,x,min(y,w)), get_min(h*2+1,w+1,r,max(x,w+1),y));
}

ll get_max(int h,int l,int r,int x,int y)
{
    if (x>y) return -1e18;
    if (l==x && y==r) return d[h].se;
    int w=(l+r)/2;
    push(h);
    return max(get_max(h*2,l,w,x,min(y,w)), get_max(h*2+1,w+1,r,max(x,w+1),y));
}

ll get(int h,int l,int r,int x)
{
    if (l==r)
    {
        return d[h].fi;
    }
    int w=(l+r)/2;
    if (x<=w) return get(h*2,l,w,x); else return get(h*2+1,w+1,r,x);
}

vector<pll> gg[1000001];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {

    n=c.size();
    q=l.size();

    for (int i = 0; i < q; i++)
    {
        gg[l[i]].pb(mp(i, v[i]));
        gg[r[i]+1].pb(mp(i, -v[i]));
    }

    vector<int> ans;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < gg[i].size(); j++)
        {
            update(1,0,q,gg[i][j].fi+1,q,gg[i][j].se);
        }

        //cout << i << " " << d[1].fi << " " << d[1].se << "\n";

        if (d[1].se-d[1].fi<c[i])
        {
            ans.pb(get(1,0,q,q)-get_min(1,0,q,0,q));
            continue;
        }

        ll l=0, r=q;
        while (l<r)
        {
            int w=(l+r+1)/2;
            if (get_max(1,0,q,w,q)-get_min(1,0,q,w,q)>=c[i]) l=w; else r=w-1;
        }

        //cout << i << " :\n";
        //cout << " l : " << l << "\n";

        ll o1=get(1,0,q,l), o2=get(1,0,q,q);
        //cout << " " << o1 << "\n";
        //cout << " " << o2 << "\n";
        assert(o1!=o2);
        if (o1<o2)
        {
            ll o3=get_max(1,0,q,l+1,q);
            ans.pb(c[i]-(o3-o2));
        }else
        {
            ll o3=get_min(1,0,q,l+1,q);
            ans.pb(o2-o3);
        }
    }

    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int j = 0; j < gg[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Incorrect 16 ms 23744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2068 ms 54068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 48076 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 16 ms 23804 KB Output is correct
3 Correct 161 ms 47240 KB Output is correct
4 Correct 463 ms 26768 KB Output is correct
5 Correct 1214 ms 50352 KB Output is correct
6 Correct 1383 ms 50380 KB Output is correct
7 Correct 1563 ms 50408 KB Output is correct
8 Correct 1130 ms 50560 KB Output is correct
9 Correct 1691 ms 50448 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Incorrect 16 ms 23744 KB Output isn't correct
3 Halted 0 ms 0 KB -