oj.uz

Submission #1038921

# Submission time Handle Problem Language Result Execution time Memory
1038921 2024-07-30T09:22:14 Z Andrey Distributing Candies (IOI21_candies) C++17
100 / 100
 911 ms 68436 KB 
#include "candies.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;

long long n,q;
vector<pair<long long,long long>> haha[200001];
vector<pair<long long,long long>> big(1000001);
vector<pair<long long,long long>> sm(1000001);
vector<long long> wow(1000001);

void build(long long l, long long r, long long x) {
    if(l == r) {
        big[x] = {0,l};
        sm[x] = {0,-l};
        return;
    }
    long long mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    big[x] = max(big[x*2],big[x*2+1]);
    sm[x] = min(sm[x*2],sm[x*2+1]);
}

void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) {
    if(l == ql && r == qr) {
        wow[x]+=br;
        big[x] = {big[x].first+br,big[x].second};
        sm[x] = {sm[x].first+br,sm[x].second};
        return;
    }
    long long mid = (l+r)/2;
    if(qr <= mid) {
        upd(l,mid,ql,qr,x*2,br);
    }
    else if(ql > mid) {
        upd(mid+1,r,ql,qr,x*2+1,br);
    }
    else {
        upd(l,mid,ql,mid,x*2,br);
        upd(mid+1,r,mid+1,qr,x*2+1,br);
    }
    big[x] = max(big[x*2],big[x*2+1]);
    sm[x] = min(sm[x*2],sm[x*2+1]);
    big[x] = {big[x].first+wow[x],big[x].second};
    sm[x] = {sm[x].first+wow[x],sm[x].second};
}

pair<long long,long long> calc(long long l, long long r, long long ql, long long qr, long long x, bool y) {
    if(ql > qr) {
        return {0,-1};
    }
    if(l == ql && r == qr) {
        if(y) {
            return big[x];
        }
        else {
            return sm[x];
        }
    }
    long long mid = (l+r)/2;
    pair<long long,long long> ans;
    if(qr <= mid) {
        ans = calc(l,mid,ql,qr,x*2,y);
    }
    else if(ql > mid) {
        ans = calc(mid+1,r,ql,qr,x*2+1,y);
    }
    else {
        pair<long long,long long> a = calc(l,mid,ql,mid,x*2,y);
        pair<long long,long long> b = calc(mid+1,r,mid+1,qr,x*2+1,y);
        if(y) {
            ans = max(a,b);
        }
        else {
            ans = min(a,b);
        }
    }
    ans = {ans.first+wow[x],ans.second};
    return ans;
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size();
    q = l.size();
    for(long long i = 0; i < q; i++) {
        haha[l[i]].push_back({v[i],q+1-i});
        haha[r[i]+1].push_back({-v[i],q+1-i});
    }
    q++;
    build(1,q,1);
    vector<int> ans(n);
    for(long long i = 0; i < n; i++) {
        for(pair<long long,long long> v: haha[i]) {
            upd(1,q,v.second,q,1,v.first);
        }
        long long bl = 0,br = q;
        while(bl < br) {
            long long mid = (br+bl+1)/2;
            if(calc(1,q,1,mid,1,1).first-calc(1,q,1,mid,1,0).first < c[i]) {
                bl = mid;
            }
            else {
                br = mid-1;
            }
        }
        long long p = bl;
        if(p == q) {
            ans[i] = calc(1,q,1,q,1,1).first;
        }
        else {
            p++;
            pair<long long,long long> a = calc(1,q,1,p,1,1);
            pair<long long,long long> b = calc(1,q,1,p,1,0);
            b = {b.first,-b.second};
            if(b.second > a.second) {
                ans[i] = a.first;
            }
            else {
                ans[i] = c[i]+b.first;
            }
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 44124 KB Output is correct
2 Correct 8 ms 44164 KB Output is correct
3 Correct 9 ms 44380 KB Output is correct
4 Correct 9 ms 44380 KB Output is correct
5 Correct 13 ms 44296 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 66412 KB Output is correct
2 Correct 896 ms 65616 KB Output is correct
3 Correct 855 ms 65688 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 44128 KB Output is correct
2 Correct 190 ms 60840 KB Output is correct
3 Correct 236 ms 50012 KB Output is correct
4 Correct 753 ms 67616 KB Output is correct
5 Correct 833 ms 67976 KB Output is correct
6 Correct 792 ms 68436 KB Output is correct
7 Correct 768 ms 67664 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 44120 KB Output is correct
2 Correct 8 ms 44292 KB Output is correct
3 Correct 86 ms 58724 KB Output is correct
4 Correct 222 ms 47960 KB Output is correct
5 Correct 639 ms 62648 KB Output is correct
6 Correct 660 ms 62644 KB Output is correct
7 Correct 682 ms 63440 KB Output is correct
8 Correct 629 ms 61616 KB Output is correct
9 Correct 555 ms 62480 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 44124 KB Output is correct
2 Correct 8 ms 44164 KB Output is correct
3 Correct 9 ms 44380 KB Output is correct
4 Correct 9 ms 44380 KB Output is correct
5 Correct 13 ms 44296 KB Output is correct
6 Correct 911 ms 66412 KB Output is correct
7 Correct 896 ms 65616 KB Output is correct
8 Correct 855 ms 65688 KB Output is correct
9 Correct 10 ms 44128 KB Output is correct
10 Correct 190 ms 60840 KB Output is correct
11 Correct 236 ms 50012 KB Output is correct
12 Correct 753 ms 67616 KB Output is correct
13 Correct 833 ms 67976 KB Output is correct
14 Correct 792 ms 68436 KB Output is correct
15 Correct 768 ms 67664 KB Output is correct
16 Correct 8 ms 44120 KB Output is correct
17 Correct 8 ms 44292 KB Output is correct
18 Correct 86 ms 58724 KB Output is correct
19 Correct 222 ms 47960 KB Output is correct
20 Correct 639 ms 62648 KB Output is correct
21 Correct 660 ms 62644 KB Output is correct
22 Correct 682 ms 63440 KB Output is correct
23 Correct 629 ms 61616 KB Output is correct
24 Correct 555 ms 62480 KB Output is correct
25 Correct 9 ms 44120 KB Output is correct
26 Correct 222 ms 48004 KB Output is correct
27 Correct 169 ms 60244 KB Output is correct
28 Correct 796 ms 66128 KB Output is correct
29 Correct 890 ms 66644 KB Output is correct
30 Correct 882 ms 66896 KB Output is correct
31 Correct 881 ms 67128 KB Output is correct
32 Correct 859 ms 67156 KB Output is correct