oj.uz

Submission #436603

# Submission time Handle Problem Language Result Execution time Memory
436603 2021-06-24T16:47:05 Z 2fat2code Distributing Candies (IOI21_candies) C++17
8 / 100
 487 ms 43548 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 200005;

int n, q;

struct item{
    ll maxi, mini, sum;
    item(){
        maxi = mini = sum = 0;
    }
};

vector<item>tree(4*nmax);

vector<pair<int,int>>RangeL[nmax], RangeR[nmax];

void update(int l, int r, int indx, ll val, int nod){
    if(l == r){
        tree[nod].maxi = tree[nod].mini = tree[nod].sum = val;
    }
    else{
        int mid = l + (r - l) / 2;
        if(indx <= mid){
            update(l, mid, indx, val, 2*nod);
        }
        else{
            update(mid+1, r, indx, val, 2*nod + 1);
        }
        tree[nod].sum = tree[2*nod].sum + tree[2*nod+1].sum;
        tree[nod].maxi = max(tree[2*nod+1].maxi, tree[2*nod].maxi + tree[2*nod+1].sum);
        tree[nod].mini = max(tree[2*nod+1].mini, tree[2*nod].mini + tree[2*nod+1].sum);
    }
}

pair<pair<ll, ll>,int> query(int l, int r, ll sufmin, ll sufmax, ll sufsum, ll val, int nod){
    if(l == r){
        pair<pair<ll,ll>,ll>it;
        it.fr.sc = min(tree[nod].mini + sufsum, sufmin);
        it.fr.fr = max(tree[nod].maxi + sufsum, sufmax);
        it.sc = tree[nod].sum;
        return it;
    }
    else{
        int mid = l + (r - l) / 2;
        pair<pair<ll,ll>,ll>it;
        it.fr.fr = max(tree[2*nod+1].maxi + sufsum, sufmax);
        it.fr.sc = min(tree[2*nod+1].mini + sufsum, sufmin);
        if(it.fr.fr - it.fr.sc >= val){
            return query(mid+1, r, sufmin, sufmax, sufsum, val, 2*nod+1);
        }
        else{
            sufmin = min(sufmin, tree[2*nod+1].mini + sufsum);
            sufmax = max(sufmax, tree[2*nod+1].maxi + sufsum);
            sufsum += tree[2*nod+1].sum;
            return query(l, mid, sufmin, sufmax, sufsum, val, 2*nod);
        }
    }
}


vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = (int)c.size();
    q = (int)l.size();
    for(int i=0;i<q;i++){
        RangeL[l[i]+1].push_back({i+1, -v[i]});
        RangeR[r[i]+1].push_back({i+1, 0});
    }
    vector<int> s(n);
    for(int i=1;i<=n;i++){
        for(auto it : RangeL[i]){
            update(1, q+1, it.fr, it.sc, 1);
        }
        auto it = query(1, q+1, 0, 0, 0, c[i-1], 1);
        if(it.fr.fr - it.fr.sc < c[i-1]){
            s[i-1] = -it.fr.sc;
        }
        else{
            if(it.sc < 0){
                if(it.fr.fr > c[i-1]) s[i-1] = 0;
                else s[i-1] = c[i - 1] - it.fr.fr;
            }
            else{
                if(-it.fr.sc > c[i-1]) s[i-1] = c[i-1];
                else s[i-1] = -it.fr.sc;
            }
        }
        for(auto it : RangeR[i]){
            update(1, q+1, it.fr, it.sc, 1);
        }
    }
    return s;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28364 KB Output is correct
2 Correct 15 ms 28444 KB Output is correct
3 Incorrect 17 ms 28576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 43472 KB Output is correct
2 Correct 487 ms 43548 KB Output is correct
3 Correct 445 ms 43460 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28364 KB Output is correct
2 Correct 15 ms 28444 KB Output is correct
3 Incorrect 17 ms 28576 KB Output isn't correct
4 Halted 0 ms 0 KB -