oj.uz

Submission #1038927

# Submission time Handle Problem Language Result Execution time Memory
1038927 2024-07-30T09:29:14 Z Andrey Distributing Candies (IOI21_candies) C++17
100 / 100
 321 ms 61784 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;
}

long long dude(long long l, long long r, long long x, long long c, long long big1, long long sm1, long long d) {
    if(l == r) {
        big1 = max(big1,big[x].first+d);
        sm1 = min(sm1,sm[x].first+d);
        if(big1-sm1 >= c) {
            return l-1;
        }
        else {
            return l;
        }
    }
    d+=wow[x];
    int mid = (l+r)/2;
    long long big2 = max(big1,big[x*2].first+d);
    long long sm2 = min(sm1,sm[x*2].first+d);
    if(big2-sm2 < c) {
        return dude(mid+1,r,x*2+1,c,big2,sm2,d);
    }
    else {
        return dude(l,mid,x*2,c,big1,sm1,d);
    }
}

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 p = dude(1,q,1,c[i],0,0,0);
        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 7 ms 44124 KB Output is correct
2 Correct 8 ms 44280 KB Output is correct
3 Correct 9 ms 44380 KB Output is correct
4 Correct 9 ms 44384 KB Output is correct
5 Correct 10 ms 44380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 61688 KB Output is correct
2 Correct 272 ms 61776 KB Output is correct
3 Correct 244 ms 61780 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 44124 KB Output is correct
2 Correct 153 ms 57848 KB Output is correct
3 Correct 63 ms 47684 KB Output is correct
4 Correct 273 ms 61780 KB Output is correct
5 Correct 283 ms 61776 KB Output is correct
6 Correct 284 ms 61748 KB Output is correct
7 Correct 254 ms 61760 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 44124 KB Output is correct
2 Correct 9 ms 44076 KB Output is correct
3 Correct 73 ms 55364 KB Output is correct
4 Correct 47 ms 46680 KB Output is correct
5 Correct 133 ms 57516 KB Output is correct
6 Correct 141 ms 57516 KB Output is correct
7 Correct 139 ms 57608 KB Output is correct
8 Correct 128 ms 57508 KB Output is correct
9 Correct 149 ms 57484 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 44124 KB Output is correct
2 Correct 8 ms 44280 KB Output is correct
3 Correct 9 ms 44380 KB Output is correct
4 Correct 9 ms 44384 KB Output is correct
5 Correct 10 ms 44380 KB Output is correct
6 Correct 254 ms 61688 KB Output is correct
7 Correct 272 ms 61776 KB Output is correct
8 Correct 244 ms 61780 KB Output is correct
9 Correct 9 ms 44124 KB Output is correct
10 Correct 153 ms 57848 KB Output is correct
11 Correct 63 ms 47684 KB Output is correct
12 Correct 273 ms 61780 KB Output is correct
13 Correct 283 ms 61776 KB Output is correct
14 Correct 284 ms 61748 KB Output is correct
15 Correct 254 ms 61760 KB Output is correct
16 Correct 8 ms 44124 KB Output is correct
17 Correct 9 ms 44076 KB Output is correct
18 Correct 73 ms 55364 KB Output is correct
19 Correct 47 ms 46680 KB Output is correct
20 Correct 133 ms 57516 KB Output is correct
21 Correct 141 ms 57516 KB Output is correct
22 Correct 139 ms 57608 KB Output is correct
23 Correct 128 ms 57508 KB Output is correct
24 Correct 149 ms 57484 KB Output is correct
25 Correct 8 ms 44124 KB Output is correct
26 Correct 56 ms 46820 KB Output is correct
27 Correct 149 ms 57680 KB Output is correct
28 Correct 262 ms 61760 KB Output is correct
29 Correct 321 ms 61784 KB Output is correct
30 Correct 270 ms 61520 KB Output is correct
31 Correct 320 ms 61776 KB Output is correct
32 Correct 294 ms 61776 KB Output is correct