oj.uz

Submission #540297

# Submission time Handle Problem Language Result Execution time Memory
540297 2022-03-19T23:57:03 Z Lyestria Distributing Candies (IOI21_candies) C++17
100 / 100
 398 ms 34188 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 2e5+10;

ll mi[mn*4], ma[mn*4], laz[mn*4];

void prop(int x){
    if(!laz[x]) return;
    mi[x] += laz[x];
    ma[x] += laz[x];
    if(x*2+1<mn*4) {
        laz[x*2]+=laz[x];
        laz[x*2+1]+=laz[x];
    }
    laz[x]=0;
}

void eval(int x){
    prop(x*2),prop(x*2+1);
    mi[x]=min(mi[x*2],mi[x*2+1]);
    ma[x]=max(ma[x*2],ma[x*2+1]);
}

const ll inf = 0x3f3f3f3f3f3f3f3f;


#define mid ((l+r)>>1)
void update(int x,int l,int r,int a,int b,int c){
    if(l==a&&r==b)laz[x]+=c;
    else {
        prop(x);
        if(b<=mid)update(x*2,l,mid,a,b,c);
        else if(a>mid)update(x*2+1,mid+1,r,a,b,c);
        else {
            update(x*2,l,mid,a,mid,c);
            update(x*2+1,mid+1,r,mid+1,b,c);
        }
        eval(x);
    }
}

ll lv;

ll query(int x,int l,int r, ll c, ll cmin=inf, ll cmax=-inf) {
    prop(x);
    if(l==r){
        cmin = min(cmin, mi[x]);
        cmax = max(cmax, ma[x]);
        // cerr << l << " " << cmin << " " << cmax << endl;
        if(cmax-cmin<c) return lv-cmin;
        else if(cmin==mi[x]) return lv-cmax+c;
        else return lv-cmin;
    }
    else {
        prop(x*2+1);
        ll ncmin = min(cmin, mi[x*2+1]), ncmax = max(cmax,ma[x*2+1]);
        // cerr << l << " " << r << " " << ncmin << " " << ncmax << " " << ncmax-ncmin-c << endl;
        if(ncmax-ncmin<c) return query(x*2,l,mid,c,ncmin,ncmax);
        else return query(x*2+1,mid+1,r,c,cmin,cmax);
    }
}


struct event {
    int t;
    int p;
    int v;
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<event> es;
    for(int i=0;i<q;i++){
        es.push_back({i+1,l[i],v[i]});
        es.push_back({i+1,r[i]+1,-v[i]});
    }
    sort(es.begin(), es.end(), [](event a, event b){
        return a.p < b.p;
    });
    auto process = [&](const event&e){
        update(1,0,q,e.t,q,e.v);
        lv+=e.v;
    };
    vector<int> ret;
    for(int i=0,j=0;i<n;i++){
        // cerr << i << endl;
        while(j<es.size() && es[j].p<=i) process(es[j++]);
        ll ans = query(1,0,q,c[i]);
        ret.push_back(ans);
    }
    return ret;
}

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:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         while(j<es.size() && es[j].p<=i) process(es[j++]);
      |               ~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 32428 KB Output is correct
2 Correct 398 ms 31600 KB Output is correct
3 Correct 380 ms 31416 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 279 ms 27332 KB Output is correct
3 Correct 64 ms 6340 KB Output is correct
4 Correct 354 ms 33472 KB Output is correct
5 Correct 374 ms 33840 KB Output is correct
6 Correct 394 ms 34188 KB Output is correct
7 Correct 352 ms 33660 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 120 ms 26928 KB Output is correct
4 Correct 85 ms 4436 KB Output is correct
5 Correct 198 ms 31064 KB Output is correct
6 Correct 192 ms 31764 KB Output is correct
7 Correct 223 ms 32312 KB Output is correct
8 Correct 193 ms 30868 KB Output is correct
9 Correct 189 ms 32440 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 376 ms 32428 KB Output is correct
7 Correct 398 ms 31600 KB Output is correct
8 Correct 380 ms 31416 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 279 ms 27332 KB Output is correct
11 Correct 64 ms 6340 KB Output is correct
12 Correct 354 ms 33472 KB Output is correct
13 Correct 374 ms 33840 KB Output is correct
14 Correct 394 ms 34188 KB Output is correct
15 Correct 352 ms 33660 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 120 ms 26928 KB Output is correct
19 Correct 85 ms 4436 KB Output is correct
20 Correct 198 ms 31064 KB Output is correct
21 Correct 192 ms 31764 KB Output is correct
22 Correct 223 ms 32312 KB Output is correct
23 Correct 193 ms 30868 KB Output is correct
24 Correct 189 ms 32440 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 68 ms 4436 KB Output is correct
27 Correct 262 ms 26944 KB Output is correct
28 Correct 338 ms 32048 KB Output is correct
29 Correct 353 ms 32432 KB Output is correct
30 Correct 371 ms 32672 KB Output is correct
31 Correct 358 ms 32944 KB Output is correct
32 Correct 364 ms 33036 KB Output is correct