oj.uz

Submission #939528

# Submission time Handle Problem Language Result Execution time Memory
939528 2024-03-06T12:57:00 Z Sundavar Distributing Candies (IOI21_candies) C++17
100 / 100
 368 ms 49848 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef pair<long long, int> plli;
struct segTree{
    struct node{
        plli mxm, mnm;
        long long lazy;
    };
    vector<node> t;
    int maxN;
    segTree(int n){
        maxN = (1<<((int)log2(n)+1));
        t.resize(2*maxN);
        for(int i = maxN; i < t.size(); i++)
            t[i].mxm = {0, i-maxN}, t[i].mnm = {0, i-maxN};
        for(int i = maxN-1; i > 0; i--)
            t[i].mxm = max(t[i*2].mxm, t[i*2+1].mxm), t[i].mnm = min(t[i*2].mnm, t[i*2+1].mnm);
    }

    void upd(int v, long long val){
        t[v].lazy += val, t[v].mxm.first += val, t[v].mnm.first += val;
    }

    void push(int v){
        upd(v*2, t[v].lazy), upd(v*2+1, t[v].lazy);
        t[v].lazy = 0;
    }

    void add(int pos, long long val){
        add(1, pos, maxN, 0, maxN, val);
    }

    void add(int v, int ll, int rr, int l, int r, long long val){
        if(min(r, rr) <= max(l, ll)) return;
        if(ll <= l && r <= rr){
            upd(v, val);
            return;
        }
        push(v);
        int m = (l+r)/2;
        add(v*2, ll, rr, l, m, val), add(v*2+1, ll, rr, m, r, val);
        t[v].mnm = min(t[v*2].mnm, t[v*2+1].mnm);
        t[v].mxm = max(t[v*2].mxm, t[v*2+1].mxm);
    }
    pair<plli, plli > find(long long c){
        return find(1, c, {-1e18, -1}, {1e18, -1});
    }
    pair<plli, plli > find(int v, long long c, plli mxm, plli mnm){
        if(v >= maxN) 
            return {max(mxm, t[v].mxm), min(mnm, t[v].mnm)};
        
        push(v);
        plli mxm2 = max(mxm, t[v*2+1].mxm), mnm2 = min(t[v*2+1].mnm, mnm);
        if(mxm2.first - mnm2.first >= c) return find(v*2+1, c, mxm, mnm);
        return find(2*v, c, mxm2, mnm2);    
    }

};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = l.size();
    std::vector<int> s(c.size());
    segTree t = segTree(n+2);
    t.add(0, 1e9+7), t.add(1, -1e9-7);
    vector<vector<plli> > diff(c.size()+1);
    long long sum = 0;
    for(int i = 0; i < n; i++){
        diff[l[i]].push_back({v[i], i+2});
        diff[r[i]+1].push_back({-v[i], i+2});
    }
    for(int i = 0; i < c.size(); i++){
        for(plli& a : diff[i]) t.add(a.second, a.first), sum += a.first;
        auto [mxm, mnm] = t.find(c[i]);
        // cout << mxm.first << " " << mxm.second << " " << mnm.first << " " << mnm.second << "\n";
        // cout << sum << "\n";
        if(mxm.second < mnm.second)
            s[i] = sum - mnm.first;
        else
            s[i] = c[i] - (mxm.first - sum);
    }
    return s;

}

/*int main(){
    distribute_candies({10, 15, 13}, {0, 0}, {1, 2}, {20, -11});
}*/

Compilation message

candies.cpp: In constructor 'segTree::segTree(int)':
candies.cpp:16:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i = maxN; i < t.size(); i++)
      |                           ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < c.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 45712 KB Output is correct
2 Correct 335 ms 45480 KB Output is correct
3 Correct 318 ms 45396 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 206 ms 36180 KB Output is correct
3 Correct 65 ms 9044 KB Output is correct
4 Correct 352 ms 46500 KB Output is correct
5 Correct 344 ms 49256 KB Output is correct
6 Correct 355 ms 49848 KB Output is correct
7 Correct 325 ms 49120 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 112 ms 36496 KB Output is correct
4 Correct 62 ms 8536 KB Output is correct
5 Correct 179 ms 43444 KB Output is correct
6 Correct 176 ms 44208 KB Output is correct
7 Correct 183 ms 47024 KB Output is correct
8 Correct 182 ms 44016 KB Output is correct
9 Correct 190 ms 46528 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 317 ms 45712 KB Output is correct
7 Correct 335 ms 45480 KB Output is correct
8 Correct 318 ms 45396 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 206 ms 36180 KB Output is correct
11 Correct 65 ms 9044 KB Output is correct
12 Correct 352 ms 46500 KB Output is correct
13 Correct 344 ms 49256 KB Output is correct
14 Correct 355 ms 49848 KB Output is correct
15 Correct 325 ms 49120 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 112 ms 36496 KB Output is correct
19 Correct 62 ms 8536 KB Output is correct
20 Correct 179 ms 43444 KB Output is correct
21 Correct 176 ms 44208 KB Output is correct
22 Correct 183 ms 47024 KB Output is correct
23 Correct 182 ms 44016 KB Output is correct
24 Correct 190 ms 46528 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 63 ms 8880 KB Output is correct
27 Correct 204 ms 37128 KB Output is correct
28 Correct 360 ms 47744 KB Output is correct
29 Correct 348 ms 48108 KB Output is correct
30 Correct 368 ms 48220 KB Output is correct
31 Correct 337 ms 48492 KB Output is correct
32 Correct 340 ms 48468 KB Output is correct