oj.uz

Submission #811160

# Submission time Handle Problem Language Result Execution time Memory
811160 2023-08-07T01:26:33 Z penguinman Distributing Candies (IOI21_candies) C++17
29 / 100
 170 ms 29288 KB 
#include "candies.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()

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();
    ll Q = l.size();
    vi max(Q+1), min(Q+1), sum(Q+1);
    per(i,Q,1){
        sum[i-1] = sum[i]+v[i-1];
        max[i-1] = std::max(max[i], sum[i-1]);
        min[i-1] = std::min(min[i], sum[i-1]);
    }
    vi left(N,-1), right(N,Q);
    while(true){
        vi mid(N);
        bool flg = true;
        vii query(Q+1);
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                query[mid[i]].pb(i);
                flg = false;
            }
        }
        if(flg) break;
        per(i,Q,0){
            for(auto el: query[i]){
                if(c[el] <= max[i]-min[i]) left[el] = mid[el];
                else right[el] = mid[el];
            }
        }
    }
    vector<int> ans(N);
    rep(i,0,N){
        if(left[i] == -1) ans[i] = max[0];
        else{
            if(v[left[i]] > 0){
                ans[i] = c[i]+min[left[i]];
            }
            else{
                ans[i] = max[left[i]];
            }
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 56 ms 14552 KB Output is correct
4 Correct 61 ms 11036 KB Output is correct
5 Correct 133 ms 27304 KB Output is correct
6 Correct 132 ms 28232 KB Output is correct
7 Correct 157 ms 29140 KB Output is correct
8 Correct 133 ms 27732 KB Output is correct
9 Correct 170 ms 29288 KB Output is correct

Subtask #5
0 / 33.0

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