oj.uz

Submission #895627

# Submission time Handle Problem Language Result Execution time Memory
895627 2023-12-30T12:04:33 Z TahirAliyev Distributing Candies (IOI21_candies) C++17
29 / 100
 708 ms 26448 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

int n, q;
const int MAX = 2e5 + 5;
int tree[4 * MAX];
array<int, 3> lazy[4 * MAX];
pii arr[MAX];

void match(int node, int ch){
    lazy[ch][0] += lazy[node][0];
    if(lazy[node][1] || lazy[node][2]){
        lazy[ch] = lazy[node];
    }
}

void relax(int node, int l, int r){
    if(!lazy[node][0] && !lazy[node][1] && !lazy[node][2]) return;
    if(lazy[node][1]) tree[node] = 0;
    if(lazy[node][2]) tree[node] = arr[r].first;
    tree[node] += lazy[node][0];
    if(l == r){
        lazy[node] = {0, 0, 0};
        return;
    }
    match(node, 2 * node);
    match(node, 2 * node + 1);
    lazy[node] = {0, 0, 0};
}

void update(int node, int l, int r, int ul, int ur, int v, int t){
    relax(node, l, r);
    if(ur < l || r < ul){
        return;
    }
    if(ul <= l && r <= ur){
        if(t == 1){
            lazy[node][0] += v;
        }
        if(t == 2){
            lazy[node] = {0, 1, 0};
        }
        if(t == 3){
            lazy[node] = {0, 0, 1};
        }
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, v, t);
    update(2 * node + 1, mid + 1, r, ul, ur, v, t);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int ask(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql) return 0;
    relax(node, l, r);
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

int f(int val, bool b){
    int l = 1, r = n;
    if(ask(1, 1, n, l, r) <= val && !b){
        return n + 1;
    }
    if(arr[r].first - ask(1, 1, n, l, r) <= val && b){
        return n + 1;
    }
    while(l < r){
        int mid = (l + r) / 2;
        if(b){
            if(arr[mid].first - ask(1, 1, n, l, mid) > val){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        else{
            if(ask(1, 1, n, l, mid) > val){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
    }
    return l;
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
    n = c.size(), q = l.size();
    for(int i = 0; i <= 4 * n; i++){
        tree[i] = 0;
        lazy[i] = {0, 0, 0};
    }
    for(int i = 1; i <= n; i++){
        arr[i] = {c[i - 1], i - 1};
    }
    sort(arr + 1, arr + n + 1);
    for(int i = 0; i < q; i++){
        if(v[i] < 0){
            int pos = f(-v[i], 0);
            update(1, 1, n, 1, pos - 1, 0, 2);
            if(pos != n + 1){
                update(1, 1, n, pos, n, v[i], 1);
            }
        }
        else{
            int pos = f(v[i], 1);
            update(1, 1, n, 1, pos - 1, 0, 3);
            if(pos != n + 1){
                update(1, 1, n, pos, n, v[i], 1);
            }
        }
    }
    vector<int> ans(n);
    for(int i = 1; i <= n; i++){
        ans[arr[i].second] = ask(1, 1, n, i, i);
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 282 ms 11856 KB Output is correct
4 Correct 90 ms 18012 KB Output is correct
5 Correct 708 ms 25072 KB Output is correct
6 Correct 682 ms 25756 KB Output is correct
7 Correct 609 ms 26340 KB Output is correct
8 Correct 639 ms 25232 KB Output is correct
9 Correct 373 ms 26448 KB Output is correct

Subtask #5
0 / 33.0

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