oj.uz

Submission #963611

# Submission time Handle Problem Language Result Execution time Memory
963611 2024-04-15T11:42:23 Z alontanay Distributing Candies (IOI21_candies) C++17
100 / 100
 468 ms 55632 KB 
#include <bits/stdc++.h>
#include "candies.h"
#define f first
#define s second
// #define DEBUGGING

#ifdef DEBUGGING
#define dout(msg) cout << msg
#else
#define dout(msg) 
#endif

using namespace std;
using ll = long long;
using pli = pair<ll,int>;

const ll INF_LL = 1e18;
const ll INF = 1e9+2;


string str(ll x) {
    return to_string(x);
}
string str(bool x) {
    return to_string(x);
}
string str(int x) {
    return to_string(x);
}

template<typename X, typename Y>
string str(pair<X,Y> p) {
    return "{" + str(p.f) + ", " + str(p.s) + "}";
}

struct Seg {
    ll segSum;
    pli maxSuf, minSuf;
    int l, r, mid;
    Seg *ls, *rs;
    Seg(int l, int r): l(l), r(r), mid((l+r)/2), segSum(0), maxSuf({0,r}), minSuf({0,-r}) {
        if(l + 1 < r) {
            ls = new Seg(l, mid);
            rs = new Seg(mid, r);
        }
    }
    void update(int i, int x) {
        if(l + 1 == r) {
            segSum = x;
            maxSuf = max(pli{x,l},pli{0,r});
            minSuf = min(pli{x,-l},pli{0,-r});
            return;
        }
        (i < mid ? ls : rs)->update(i,x);
        segSum = ls->segSum + rs->segSum;
        maxSuf = max(rs->maxSuf, pli{ls->maxSuf.f+rs->segSum,ls->maxSuf.s});
        minSuf = min(rs->minSuf, pli{ls->minSuf.f+rs->segSum,ls->minSuf.s});
    }
    ll sumSuffix(int i) {
        if(l + 1 == r) {
            return i < r ? segSum : 0LL;
        }
        if(i < mid) {
            return ls->sumSuffix(i) + rs->segSum;
        }
        return rs->sumSuffix(i);
    }
    pair<ll,bool> findLastBound(ll c, pli mx, pli mn, ll sumr) {
        if(l + 1 == r) {
            return segSum < 0 ? pair<ll,bool>{mx.s,false} : pair<ll,bool>{-mn.s,true};
        }
        pli rmx = max(mx, {rs->maxSuf.f + sumr, rs->maxSuf.s});
        pli rmn = min(mn, {rs->minSuf.f + sumr, rs->minSuf.s});
        dout(str(mx) << ' ' << str(mn) << " | " << str(rmx) << ' ' << str(rmn) << endl);
        dout("   " << rmx.f - rmn.f << " >= " << c << endl);
        if(rmx.f - rmn.f >= c) {
            return rs->findLastBound(c, mx, mn, sumr);
        }
        return ls->findLastBound(c, rmx, rmn, sumr + rs->segSum);
    }
    pair<ll,bool> findLastBound(ll c) {
        return findLastBound(c, pli{0,r}, pli{0,-r},0);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    Seg seg(0, q+1);
    seg.update(0,-INF);
    vector<vector<int>> upds(n+1);
    for(int qi = 0; qi < q; qi ++) {
        upds[l[qi]].push_back(qi);
        upds[r[qi]+1].push_back(qi+q);
    }
    vector<int> res(n);
    for(int i = 0; i < n; i ++) {
        for(int upd : upds[i]) {
            int x, y;
            if(upd >= q) {
                x = upd-q+1;
                y = 0;
                seg.update(upd-q+1,0);
            } else {
                x = upd +1;
                y = v[upd];
                seg.update(upd+1,v[upd]);
            }
            dout("UPD " << x << ' ' << y << endl);
        }
        dout(seg.maxSuf.f << ' ' << seg.maxSuf.s << " | " << seg.minSuf.f << ' ' << seg.minSuf.s << endl);
        pair<ll,bool> lastBound = seg.findLastBound(c[i]);
        dout(lastBound.f << endl);
        res[i] = seg.sumSuffix(lastBound.f);
        if(lastBound.s) {
            res[i] += c[i];
        }
    }
    return res;
}

Compilation message

candies.cpp: In constructor 'Seg::Seg(int, int)':
candies.cpp:39:15: warning: 'Seg::mid' will be initialized after [-Wreorder]
   39 |     int l, r, mid;
      |               ^~~
candies.cpp:37:8: warning:   'll Seg::segSum' [-Wreorder]
   37 |     ll segSum;
      |        ^~~~~~
candies.cpp:41:5: warning:   when initialized here [-Wreorder]
   41 |     Seg(int l, int r): l(l), r(r), mid((l+r)/2), segSum(0), maxSuf({0,r}), minSuf({0,-r}) {
      |     ^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:99:17: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   99 |             int x, y;
      |                 ^
candies.cpp:99:20: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   99 |             int x, y;
      |                    ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 52948 KB Output is correct
2 Correct 411 ms 53328 KB Output is correct
3 Correct 421 ms 52820 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 311 ms 41564 KB Output is correct
3 Correct 60 ms 10064 KB Output is correct
4 Correct 446 ms 55012 KB Output is correct
5 Correct 438 ms 55396 KB Output is correct
6 Correct 408 ms 55632 KB Output is correct
7 Correct 390 ms 55120 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 97 ms 40744 KB Output is correct
4 Correct 49 ms 9052 KB Output is correct
5 Correct 152 ms 48588 KB Output is correct
6 Correct 151 ms 49480 KB Output is correct
7 Correct 166 ms 50064 KB Output is correct
8 Correct 158 ms 48752 KB Output is correct
9 Correct 153 ms 49956 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 405 ms 52948 KB Output is correct
7 Correct 411 ms 53328 KB Output is correct
8 Correct 421 ms 52820 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 311 ms 41564 KB Output is correct
11 Correct 60 ms 10064 KB Output is correct
12 Correct 446 ms 55012 KB Output is correct
13 Correct 438 ms 55396 KB Output is correct
14 Correct 408 ms 55632 KB Output is correct
15 Correct 390 ms 55120 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 97 ms 40744 KB Output is correct
19 Correct 49 ms 9052 KB Output is correct
20 Correct 152 ms 48588 KB Output is correct
21 Correct 151 ms 49480 KB Output is correct
22 Correct 166 ms 50064 KB Output is correct
23 Correct 158 ms 48752 KB Output is correct
24 Correct 153 ms 49956 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 51 ms 9192 KB Output is correct
27 Correct 300 ms 41428 KB Output is correct
28 Correct 432 ms 53552 KB Output is correct
29 Correct 410 ms 54032 KB Output is correct
30 Correct 468 ms 54356 KB Output is correct
31 Correct 423 ms 54240 KB Output is correct
32 Correct 425 ms 54384 KB Output is correct