oj.uz

Submission #799560

# Submission time Handle Problem Language Result Execution time Memory
799560 2023-07-31T15:59:35 Z TheSahib Distributing Candies (IOI21_candies) C++17
29 / 100
 565 ms 23580 KB 
#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

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.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 220 ms 7772 KB Output is correct
4 Correct 82 ms 15304 KB Output is correct
5 Correct 542 ms 22176 KB Output is correct
6 Correct 542 ms 22900 KB Output is correct
7 Correct 565 ms 23392 KB Output is correct
8 Correct 535 ms 22080 KB Output is correct
9 Correct 304 ms 23500 KB Output is correct

Subtask #5
0 / 33.0

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