oj.uz

Submission #1070255

# Submission time Handle Problem Language Result Execution time Memory
1070255 2024-08-22T12:31:15 Z ArthuroWich Distributing Candies (IOI21_candies) C++17
100 / 100
 1582 ms 54272 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int segs[4*200005], segmx[4*200005], segmn[4*200005], lazy[4*200005];
void lazypropagate(int n, int l, int r) {
    if (lazy[n]) {
        segmn[n] += lazy[n];
        segmx[n] += lazy[n];
        if (l != r) {
            lazy[2*n] += lazy[n];
            lazy[2*n+1] += lazy[n];
        }
        lazy[n] = 0;
    }
}
void updates(int n, int l, int r, int i, int v) {
    if (l == r) {
        segs[n] += v;
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            updates(2*n, l, m, i, v);
        } else {
            updates(2*n+1, m+1, r, i, v);
        }
        segs[n] = segs[2*n] + segs[2*n+1];
    }
}
void updatem(int n, int l, int r, int a, int b, int v) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        lazy[n] += v;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        updatem(2*n, l, m, a, b, v);
        updatem(2*n+1, m+1, r, a, b, v);
        segmn[n] = min(segmn[2*n], segmn[2*n+1]);
        segmx[n] = max(segmx[2*n], segmx[2*n+1]);
    }
}
int querys(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return 0;
    } else if (a <= l && r <= b) {
        return segs[n];
    } else {
        int m = (l+r)/2;
        return querys(2*n, l, m, a, b) + querys(2*n+1, m+1, r, a, b);
    }
}
int querymn(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT64_MAX;
    }
    lazypropagate(n, l, r); 
    if (a <= l && r <= b) {
        return segmn[n];
    } else {
        int m = (l+r)/2;
        return min(querymn(2*n, l, m, a, b), querymn(2*n+1, m+1, r, a, b));
    }
}
int querymx(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT64_MIN;
    }
    lazypropagate(n, l, r); 
    if (a <= l && r <= b) {
        return segmx[n];
    } else {
        int m = (l+r)/2;
        return max(querymx(2*n, l, m, a, b), querymx(2*n+1, m+1, r, a, b));
    }
}
int trav(int q, int c) {
    int l = 0, r = q;
    while(l < r) {
        int m = (l+r+1)/2;
        if (querymx(1, 0, q, m, q)-querymn(1, 0, q, m, q) > c) {
            l = m;
        } else {
            r = m-1;
        }
    }
    if (querymx(1, 0, q, l, q)-querymn(1, 0, q, l, q) > c) {
        return l;
    } else {
        return -1;
    }
}
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
    int n = c.size(), q = l.size();
    vector<int32_t> ans(n);
    vector<vector<int>> le(n), ri(n);
    for (int i = 1; i <= q; i++) {
        le[l[i-1]].push_back(i);
        if (r[i-1]+1 < n) {
            ri[r[i-1]+1].push_back(i);
        }
        //updatem(1, 0, q, i, q, v[i-1]);
        //updates(1, 0, q, i, v[i-1]);
    }
    for (int i = 0; i < n; i++) {
        for (int j : le[i]) {
            updatem(1, 0, q, j, q, v[j-1]);
            updates(1, 0, q, j, v[j-1]);
        }
        for (int j : ri[i]) {
            updatem(1, 0, q, j, q, -v[j-1]);
            updates(1, 0, q, j, -v[j-1]);
        }
        int ind = trav(q, c[i]);    
        if (ind == -1) {
            ans[i] = segs[1]-querymn(1, 0, q, 0, q);
            continue; 
        }
        if (segs[1] > querys(1, 0, q, 0, ind)) {
            ans[i] = c[i]-(querymx(1, 0, q, ind, q)-segs[1]);
        } else {
            ans[i] = segs[1]-querymn(1, 0, q, ind, q);
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 7 ms 6852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1465 ms 51280 KB Output is correct
2 Correct 1582 ms 51536 KB Output is correct
3 Correct 1572 ms 51284 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 356 ms 32248 KB Output is correct
3 Correct 448 ms 14592 KB Output is correct
4 Correct 1556 ms 47076 KB Output is correct
5 Correct 1521 ms 53876 KB Output is correct
6 Correct 1409 ms 54272 KB Output is correct
7 Correct 1376 ms 53484 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6588 KB Output is correct
3 Correct 114 ms 31916 KB Output is correct
4 Correct 438 ms 19652 KB Output is correct
5 Correct 1232 ms 44400 KB Output is correct
6 Correct 1241 ms 44916 KB Output is correct
7 Correct 1156 ms 45176 KB Output is correct
8 Correct 1128 ms 44408 KB Output is correct
9 Correct 1130 ms 44992 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 7 ms 6852 KB Output is correct
6 Correct 1465 ms 51280 KB Output is correct
7 Correct 1582 ms 51536 KB Output is correct
8 Correct 1572 ms 51284 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 356 ms 32248 KB Output is correct
11 Correct 448 ms 14592 KB Output is correct
12 Correct 1556 ms 47076 KB Output is correct
13 Correct 1521 ms 53876 KB Output is correct
14 Correct 1409 ms 54272 KB Output is correct
15 Correct 1376 ms 53484 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6588 KB Output is correct
18 Correct 114 ms 31916 KB Output is correct
19 Correct 438 ms 19652 KB Output is correct
20 Correct 1232 ms 44400 KB Output is correct
21 Correct 1241 ms 44916 KB Output is correct
22 Correct 1156 ms 45176 KB Output is correct
23 Correct 1128 ms 44408 KB Output is correct
24 Correct 1130 ms 44992 KB Output is correct
25 Correct 1 ms 6488 KB Output is correct
26 Correct 433 ms 13656 KB Output is correct
27 Correct 243 ms 36120 KB Output is correct
28 Correct 1494 ms 52112 KB Output is correct
29 Correct 1469 ms 52304 KB Output is correct
30 Correct 1442 ms 52700 KB Output is correct
31 Correct 1409 ms 52900 KB Output is correct
32 Correct 1406 ms 53100 KB Output is correct