oj.uz

Submission #447527

# Submission time Handle Problem Language Result Execution time Memory
447527 2021-07-26T16:22:23 Z Josia Distributing Candies (IOI21_candies) C++17
0 / 100
 3142 ms 86136 KB 
#include "candies.h"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int int64_t

vector<int> lazy;

vector<pair<pair<int, int>, pair<int, int>>> tree;


void push(int v) {
    lazy[v*2] += lazy[v];
    lazy[v*2+1] += lazy[v];
    tree[v*2].first.first += lazy[v];
    tree[v*2+1].first.first += lazy[v];
    tree[v*2].second.first += lazy[v];
    tree[v*2+1].second.first += lazy[v];
    lazy[v] = 0;
}


void update(int v, int rl, int rr, int ql, int qr, int x) {
    push(v);
    if (qr < ql) return;
    if (rl == ql && rr == qr) {
        tree[v].first.first += x;
        tree[v].second.first += x;
        lazy[v] += x;
        return;
    }
    int rm = (rl + rr) / 2;

    update(v*2, rl, rm, ql, min(rm, qr), x);
    update(v*2+1, rm+1, rr, max(rm+1, ql), qr, x);
    tree[v].first = min(tree[v*2].first, tree[v*2+1].first);
    tree[v].second = max(tree[v*2].second, tree[v*2+1].second);
}

pair<pair<int, int>, pair<int, int>> querry(int v, int rl, int rr, int ql, int qr) {
    push(v);
    if (qr < ql) return {{INT64_MAX, -1}, {INT64_MIN, -1}};
    if (rl == ql && rr == qr) {
        return tree[v];
    }
    int rm = (rl + rr) / 2;

    pair<pair<int, int>, pair<int, int>> left = querry(v*2, rl, rm, ql, min(rm, qr));
    pair<pair<int, int>, pair<int, int>> right = querry(v*2+1, rm+1, rr, max(rm+1, ql), qr);

    pair<pair<int, int>, pair<int, int>> res;
    res.first = min(left.first, right.first);
    res.second = max(left.second, right.second);

    return res;
}


void build(int v, int rl, int rr) {
    if (rl == rr) {
        tree[v] = {{0, rl}, {0, rl}};
    }
    else {
        int rm = (rl + rr) / 2;
        build(v*2, rl, rm);
        build(v*2+1, rm+1, rr);
    }
}


std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l, std::vector<signed> r, std::vector<signed> v) {
    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    reverse(v.begin(), v.end());
    
    l.push_back(0);
    r.push_back(c.size()-1);
    v.push_back(0);

    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    reverse(v.begin(), v.end());
    

    
    lazy.assign(l.size()*8, 0);
    tree.assign(l.size()*8, {{0, -1}, {0, -1}});

    vector<signed> listOfOutputs;

    build(1, 0, l.size()-1);


    vector<vector<pair<int, bool>>> events(c.size()+1);

    for (int i = 0; i<l.size(); i++) {
        events[l[i]].push_back({i, 0});
        events[r[i]+1].push_back({i, 1});
    }

    // cout << "EVENTS:\n";
    // for (auto i: events) {
    //     cout << "level\n";
    //     for (auto j: i)
    //         cout << j.first << " " << j.second << "\n";
    // }

    
    for (int i = 0; i<c.size(); i++) {
        for (auto j: events[i]) {
            if (j.second) {
                update(1, 0, l.size()-1, j.first, l.size()-1, -v[j.first]);
            } else {
                update(1, 0, l.size()-1, j.first, l.size()-1, v[j.first]);
            }
        }




        int left = 0; int right = l.size()-1;
        pair<pair<int, int>, pair<int, int>> res;
        while(left<right) {
            int m = (left+right) / 2;
            res = querry(1, 0, l.size()-1, l.size()-1-m, l.size()-1);
            if (res.second.first - res.first.first >= c[i]) right = m;
            else left = m+1;
        }
        res = querry(1, 0, l.size()-1, l.size()-1-left, l.size()-1);

        int output;

        // cout << res.first.first << " " << res.first.second << " " << res.second.first << " " << res.second.second << "\n";


        if (res.second.first - res.first.first >= c[i]) {
            if (res.first.second > res.second.second) {
                output = querry(1, 0, l.size()-1, l.size()-1, l.size()-1).first.first - res.first.first;
                // cout << "min\n";
            } else {
                output = c[i] - (res.second.first - querry(1, 0, l.size()-1, l.size()-1, l.size()-1).first.first);
                // cout << "max\n";
            }
        } else {
            output = querry(1, 0, l.size()-1, l.size()-1, l.size()-1).first.first;
            // cout << "other\n";
        }

        listOfOutputs.push_back(output);
    }

    return listOfOutputs;

}

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:100:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i<l.size(); i++) {
      |                     ~^~~~~~~~~
candies.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i<c.size(); i++) {
      |                     ~^~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3142 ms 86136 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 204 KB Output isn't correct
2 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 1 ms 332 KB Output is correct
3 Incorrect 238 ms 75304 KB Output isn't correct
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 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -