oj.uz

Submission #923401

# Submission time Handle Problem Language Result Execution time Memory
923401 2024-02-07T07:25:05 Z Edwin0319 Distributing Candies (IOI21_candies) C++17
0 / 100
 141 ms 12456 KB 
#include "candies.h"

#include <vector>

struct node{
    int tag, num;
} trees[200005 << 2];

inline int ls(int p){return p << 1;}

inline int rs(int p){return p << 1 | 1;}

void push_Down(int l, int r, int p){
    int lc = ls(p), rc = rs(p);
    trees[lc].tag += trees[p].tag;
    trees[rc].tag += trees[p].tag;
    // trees[lc].num += trees[p].tag * (MID - l + 1);
    // trees[rc].num += trees[p].tag * (r - MID);
    trees[p].tag = 0;
    return;
}

// void push_Up(int p){
//     trees[p].num = trees[ls(p)].num + trees[rs(p)].num;
//     return;
// }

// void build(int l, int r, int p, std::vector<int> &a){
//     trees[p].tag = 0;
//     if(l == r){
//         trees[p].num = a[l];
//         return;
//     }
//     int MID = (l + r) >> 1;
//     build()
// }

void update(int l, int r, int nl, int nr, int p, int k){
    if(nl <= l && r <= nr){
        trees[p].tag += k;
        // trees[p].num += k * (r - l + 1);
        return;
    }
    push_Down(l, r, p);
    int MID = (l + r) >> 1;
    if(MID >= nl) update(l, MID, nl, nr, ls(p), k);
    if(MID + 1 <= nr) update(MID + 1, r, nl, nr, rs(p), k);
    // push_Up(p);
    return;
}

int query(int l, int r, int n, int p){
    if(l == r && l == n){
        return p;
    }
    push_Down(l, r, p);
    int MID = (l + r) >> 1;
    if(MID >= n) return query(l, MID, n, ls(p));
    else return query(MID + 1, r, n, rs(p));
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size(), m = l.size();
    c.insert(c.begin(), 0);
    l.insert(l.begin(), 0);
    r.insert(r.begin(), 0);
    v.insert(v.begin(), 0);
    std::vector<int> s(n);
    for(int i = 1; i <= m; i++){
        // printf("%d %d %d\n", l[i] + 1, r[i] + 1, v[i]);
        update(1, n, l[i] + 1, r[i] + 1, 1, v[i]);
    }
    for(int i = 1; i <= n; i++){
        int p = query(1, n, i, 1);
        s[i - 1] = trees[p].tag >= c[i] ? c[i] : trees[p].tag;
    }
    return s;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 12456 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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