oj.uz

Submission #1101458

# Submission time Handle Problem Language Result Execution time Memory
1101458 2024-10-16T08:43:56 Z Dan4Life Distributing Candies (IOI21_candies) C++17
27 / 100
 437 ms 24396 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
const int mxN = (int)2e5+10;
const ll LINF = (ll)1e18;
int n, q;
ll mxsuf[mxN], mnsuf[mxN], pref[mxN];
array<ll,3> seg[mxN*2], Init={LINF,-LINF, 0ll};

void apply(int p, ll a, ll b, ll c){
    seg[p][0] = min(a, max(seg[p][0]+c, b));
    seg[p][1] = max(seg[p][1]+c, b);
    seg[p][2] += c;
}

void prop(int p, int l, int r){
    if(l==r or seg[p]==Init) return;
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    auto [a,b,c] = seg[p]; // push down
    apply(p+1,a,b,c), apply(rp,a,b,c); seg[p] = Init;
}
 
void upd(int i, int j, ll a, ll b, ll c, int p=0, int l=0, int r=n-1){
    if(i>j or i>r or j<l) return;
    if(i<=l and r<=j){ apply(p,a,b,c); return; }
    prop(p,l,r); // propagate to preserve order
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    upd(i,j,a,b,c,p+1,l,mid); upd(i,j,a,b,c,rp,mid+1,r);
}
 
ll query(int i, int p=0, int l=0, int r=n-1){
    if(l==r) return min(seg[p][0],max(seg[p][2],seg[p][1]));
    prop(p,l,r); // propagate to preserve order
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(i<=mid) return query(i,p+1,l,mid);
    return query(i,rp,mid+1,r);
}

vi distribute_candies(vi c, vi l, vi r, vi v){
    n = sz(c), q = sz(l); 
    vector<int> ans(n,0);
    fill(seg, seg+n*2,Init);
    for(int i = 0; i < q; i++){
        upd(l[i],r[i],LINF,-LINF,v[i]);
        upd(l[i],r[i],c[l[i]],-LINF,0);
        upd(l[i],r[i],LINF,0,0);
    }
    for(int i = 0; i < n; i++) ans[i]=query(i);
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 414 ms 22604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 222 ms 8416 KB Output is correct
3 Correct 68 ms 16552 KB Output is correct
4 Correct 437 ms 23628 KB Output is correct
5 Correct 419 ms 24256 KB Output is correct
6 Correct 428 ms 24396 KB Output is correct
7 Correct 410 ms 23884 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -