Submission #923397

#	Time	Username	Problem	Language	Result	Execution time	Memory
923397		Edwin0319	Distributing Candies (IOI21_candies)	C++17	0 / 100	155 ms	15176 KiB

candies

#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), MID = (l + r) >> 1;
    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;
}

Compilation message (stderr)

candies.cpp: In function 'void push_Down(int, int, int)':
candies.cpp:14:33: warning: unused variable 'MID' [-Wunused-variable]
   14 |     int lc = ls(p), rc = rs(p), MID = (l + r) >> 1;
      |                                 ^~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33