oj.uz

Submission #942491

# Submission time Handle Problem Language Result Execution time Memory
942491 2024-03-10T18:02:02 Z KG07 Distributing Candies (IOI21_candies) C++17
100 / 100
 341 ms 49548 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

struct segment_tree{
    long long vmax[800008], vmin[800008], lazy[800008], m;
    int n;
    void init(int N){
        n = N;
        m = 0LL;
        for(int i = 0; i < 800008; i++){
            vmax[i] = 0LL;
            vmin[i] = 0LL;
            lazy[i] = 0LL;
        }
    }
    void lazy_update(int N){
        lazy[2*N] += lazy[N];
        lazy[2*N+1] += lazy[N];
        vmax[2*N] += lazy[N];
        vmin[2*N] += lazy[N];
        vmax[2*N+1] += lazy[N];
        vmin[2*N+1] += lazy[N];
        lazy[N] = 0;
    }
    long long get_max(int N, int l, int r, int s, int t){
        if(l > t || s > r)return -9000000000000000000LL;
        if(l <= s && t <= r)return vmax[N];
        lazy_update(N);
        return max(get_max(2*N, l, r, s, (s+t)/2), get_max(2*N+1, l, r, (s+t)/2+1, t));
    }
    long long get_min(int N, int l, int r, int s, int t){
        if(l > t || s > r)return 9000000000000000000LL;
        if(l <= s && t <= r)return vmin[N];
        lazy_update(N);
        return min(get_min(2*N, l, r, s, (s+t)/2), get_min(2*N+1, l, r, (s+t)/2+1, t));
    }
    void update(int N, long long M, int l, int r, int s, int t){
        if(s == 1 && t == n)m += M;
        if(l > t || s > r)return;
        if(l <= s && t <= r){
            vmax[N] += M;
            vmin[N] += M;
            lazy[N] += M;
            return;
        }
        lazy_update(N);
        update(2*N, M, l, r, s, (s+t)/2);
        update(2*N+1, M, l, r, (s+t)/2+1, t);
        vmax[N] = max(vmax[2*N], vmax[2*N+1]);
        vmin[N] = min(vmin[2*N], vmin[2*N+1]);
    }
    pair<long long, long long> find_index(int N, long long M, int l, int r, long long s, long long t){
        if(l == r)return make_pair(vmax[N], max(s, vmax[N])+min(t, vmin[N])-vmin[N]);
        lazy_update(N);
        if(max(s, vmax[2*N+1])-min(t, vmin[2*N+1])<M)return find_index(2*N, M, l, (l+r)/2, max(s, vmax[2*N+1]), min(t, vmin[2*N+1]));
        return find_index(2*N+1, M, (l+r)/2+1, r, s, t);
    }
} A;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
    A.init(q+1);
    vector<vector<int>> x(n), y(n);
    for(int i = 0; i < q; i++){
        x[l[i]].push_back(i);
        if(r[i]<n-1)y[r[i]+1].push_back(i);
    }
    vector<int> s(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < x[i].size(); j++)A.update(1, v[x[i][j]], x[i][j]+2, q+1, 1, q+1);
        for(int j = 0; j < y[i].size(); j++)A.update(1, -v[y[i][j]], y[i][j]+2, q+1, 1, q+1);
        //for(int j = 1; j < 6; j++)cout << A.vmax[j] << " " << A.vmin[j] << " " << A.lazy[j] << "\n";
        pair<long long, long long> t = A.find_index(1, c[i], 1, q+1, -9000000000000000000LL, 9000000000000000000LL);
        if(abs(t.first-t.second) >= c[i])s[i] = t.first > t.second ? A.m - t.second : A.m - t.second + c[i];
        else s[i] = max(0LL, A.m - A.get_min(1, 1, q+1, 1, q+1));
    }

    return s;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j = 0; j < x[i].size(); j++)A.update(1, v[x[i][j]], x[i][j]+2, q+1, 1, q+1);
      |                        ~~^~~~~~~~~~~~~
candies.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 0; j < y[i].size(); j++)A.update(1, -v[y[i][j]], y[i][j]+2, q+1, 1, q+1);
      |                        ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19544 KB Output is correct
4 Correct 4 ms 19288 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 42836 KB Output is correct
2 Correct 309 ms 46932 KB Output is correct
3 Correct 333 ms 46756 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 169 ms 26872 KB Output is correct
3 Correct 50 ms 33328 KB Output is correct
4 Correct 317 ms 48764 KB Output is correct
5 Correct 304 ms 48976 KB Output is correct
6 Correct 288 ms 49548 KB Output is correct
7 Correct 341 ms 48888 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 86 ms 24964 KB Output is correct
4 Correct 49 ms 30812 KB Output is correct
5 Correct 144 ms 36552 KB Output is correct
6 Correct 142 ms 36548 KB Output is correct
7 Correct 149 ms 36596 KB Output is correct
8 Correct 144 ms 36460 KB Output is correct
9 Correct 134 ms 36456 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19544 KB Output is correct
4 Correct 4 ms 19288 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 292 ms 42836 KB Output is correct
7 Correct 309 ms 46932 KB Output is correct
8 Correct 333 ms 46756 KB Output is correct
9 Correct 3 ms 19032 KB Output is correct
10 Correct 169 ms 26872 KB Output is correct
11 Correct 50 ms 33328 KB Output is correct
12 Correct 317 ms 48764 KB Output is correct
13 Correct 304 ms 48976 KB Output is correct
14 Correct 288 ms 49548 KB Output is correct
15 Correct 341 ms 48888 KB Output is correct
16 Correct 3 ms 19032 KB Output is correct
17 Correct 3 ms 19036 KB Output is correct
18 Correct 86 ms 24964 KB Output is correct
19 Correct 49 ms 30812 KB Output is correct
20 Correct 144 ms 36552 KB Output is correct
21 Correct 142 ms 36548 KB Output is correct
22 Correct 149 ms 36596 KB Output is correct
23 Correct 144 ms 36460 KB Output is correct
24 Correct 134 ms 36456 KB Output is correct
25 Correct 3 ms 19032 KB Output is correct
26 Correct 49 ms 32340 KB Output is correct
27 Correct 158 ms 29268 KB Output is correct
28 Correct 310 ms 47336 KB Output is correct
29 Correct 299 ms 47700 KB Output is correct
30 Correct 290 ms 47984 KB Output is correct
31 Correct 294 ms 47956 KB Output is correct
32 Correct 306 ms 48392 KB Output is correct