oj.uz

Submission #447628

# Submission time Handle Problem Language Result Execution time Memory
447628 2021-07-27T07:07:04 Z Josia Distributing Candies (IOI21_candies) C++17
100 / 100
 3447 ms 100684 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}};
        return;
    }
    int rm = (rl + rr) / 2;
    build(v*2, rl, rm);
    build(v*2+1, rm+1, rr);
    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);
}


std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l, std::vector<signed> r, std::vector<signed> v) {
    // freopen("output.txt","w",stdout);

    
    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()*9, 0);
    tree.assign(l.size()*9, {{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]);
            }
        }


        // cout << "TREE:\n";
        // for (int j = 0; j<l.size(); j++) {
        //     cout << querry(1, 0, l.size()-1, j, min(j+1, int(l.size()-1))).first.first << " ";
        // }
        // cout << "\n";



        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);
            // cout << res.first.first << " " << res.first.second << " " << res.second.first << " " << res.second.second << "\n";
        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 - querry(1, 0, l.size()-1, 0, 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:104: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]
  104 |     for (int i = 0; i<l.size(); i++) {
      |                     ~^~~~~~~~~
candies.cpp:116: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]
  116 |     for (int i = 0; i<c.size(); i++) {
      |                     ~^~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 1100 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 13 ms 1300 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3416 ms 96292 KB Output is correct
2 Correct 3372 ms 98128 KB Output is correct
3 Correct 3447 ms 97888 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 596 ms 87368 KB Output is correct
3 Correct 874 ms 10720 KB Output is correct
4 Correct 3351 ms 99792 KB Output is correct
5 Correct 3309 ms 100272 KB Output is correct
6 Correct 3249 ms 100684 KB Output is correct
7 Correct 3157 ms 99960 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 240 ms 85416 KB Output is correct
4 Correct 925 ms 9644 KB Output is correct
5 Correct 2854 ms 93364 KB Output is correct
6 Correct 2826 ms 93928 KB Output is correct
7 Correct 2872 ms 94576 KB Output is correct
8 Correct 2832 ms 93332 KB Output is correct
9 Correct 2695 ms 94636 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 1100 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 13 ms 1300 KB Output is correct
6 Correct 3416 ms 96292 KB Output is correct
7 Correct 3372 ms 98128 KB Output is correct
8 Correct 3447 ms 97888 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 596 ms 87368 KB Output is correct
11 Correct 874 ms 10720 KB Output is correct
12 Correct 3351 ms 99792 KB Output is correct
13 Correct 3309 ms 100272 KB Output is correct
14 Correct 3249 ms 100684 KB Output is correct
15 Correct 3157 ms 99960 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 240 ms 85416 KB Output is correct
19 Correct 925 ms 9644 KB Output is correct
20 Correct 2854 ms 93364 KB Output is correct
21 Correct 2826 ms 93928 KB Output is correct
22 Correct 2872 ms 94576 KB Output is correct
23 Correct 2832 ms 93332 KB Output is correct
24 Correct 2695 ms 94636 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 862 ms 9848 KB Output is correct
27 Correct 610 ms 86944 KB Output is correct
28 Correct 3314 ms 98532 KB Output is correct
29 Correct 3330 ms 98792 KB Output is correct
30 Correct 3350 ms 99072 KB Output is correct
31 Correct 3192 ms 99336 KB Output is correct
32 Correct 3353 ms 99464 KB Output is correct