Submission #799560

#	Time	Username	Problem	Language	Result	Execution time	Memory
799560		TheSahib	Distributing Candies (IOI21_candies)	C++17	29 / 100	565 ms	23580 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<ll, ll>

using namespace std;

const int MAX = 2e5 + 5;

pii tree[MAX * 4];
ll maxC = 0;

void relax(int node, int l, int r){
    if((tree[node].first == 0 && tree[node].second == 0) || l == r) return;
    if(tree[node].first == 0){
        tree[node * 2].second += tree[node].second;
        tree[node * 2 + 1].second += tree[node].second;
    }
    else{
        tree[node * 2] = tree[node];
        tree[node * 2 + 1] = tree[node];
    }
    tree[node] = {0, 0};
}

vector<pii> abc;
map<int, int> mp;

void update(int node, int l, int r, int ql, int qr, pii val){
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr){
        if(val.first){
            tree[node] = val;
        }
        else{
            tree[node].second += val.second;
        }
        return;
    }
    relax(node, l, r);
    int mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr, val);
    update(node * 2 + 1, mid + 1, r, ql, qr, val);
}
ll get(int node, int l, int r, int pos){
    if(l == r){
        ll ans = 0;
        if(tree[node].first == 1) ans = abc[l].first;
        ans += tree[node].second; 
        return ans;
    }
    relax(node, l, r);
    int mid = (l + r) / 2;
    if(pos <= mid){
        return get(node * 2, l, mid, pos);
    }
    else{
        return get(node * 2 + 1, mid + 1, r, pos);
    }
}


std::vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    maxC = c[0];
    int n = c.size();
    for (int i = 0; i < n; i++)
    {
        abc.push_back({c[i], i});
    }
    sort(abc.begin(), abc.end());
    
    for (int i = 0; i < l.size(); i++)
    {
        update(1, 0, n - 1, l[i], r[i], {0, v[i]});
        
        int lw = 0, hg = n - 1;
        int b = -1;
        while(lw <= hg){
            int mid = (lw + hg) / 2;
            ll a = get(1, 0, n - 1, mid);
            if((v[i] > 0 && a >= abc[mid].first) || (v[i] < 0 && a <= 0)){
                lw = mid + 1;
                b = mid;
            }
            else{
                hg = mid - 1;
            }
        }
        if(b == -1) continue;
        update(1, 0, n - 1, 0, b, {(v[i] > 0) ? 1ll: -1ll, 0ll});
    }
    vector<int> ans(c.size());
    for (int i = 0; i < c.size(); i++)
    {
        ans[abc[i].second] = get(1, 0, n - 1, i);
    }
    return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33