oj.uz

Submission #466684

# Submission time Handle Problem Language Result Execution time Memory
466684 2021-08-20T07:18:11 Z JvThunder Distributing Candies (IOI21_candies) C++17
29 / 100
 142 ms 15560 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int MAXQ = 1000005;
const ll INF = (ll)(1e18);

vector<int> distribute_candies(vector<int> c, vector<int> L, vector<int> R, vector<int> v) 
{
    int n = c.size(); int q = v.size();
    
    vector<ll> p;
    p.push_back(INF); p.push_back(0LL);
    for(int i=0;i<q;i++) p.push_back(p.back()+v[i]);
    q+=2;

    vector<ll> smax(q),smin(q);
    smax[q-1] = smin[q-1] = p[q-1];
    for(int i=q-2;i>=0;i--)
    {
        smax[i] = max(smax[i+1],p[i]);
        smin[i] = min(smin[i+1],p[i]);
    }

    vector<int> final_A(n);
    for(int i=0;i<n;i++)
    {
        int l = 0; int r = q-1;
        int ret = -1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(smax[mid]-smin[mid]<c[i]) r = mid-1;
            else ret = mid, l = mid+1;
        }
        if(p[ret]==smax[ret]) final_A[i] = 0+(p[q-1]-smin[ret]);
        if(p[ret]==smin[ret]) final_A[i] = c[i]-(smax[ret]-p[q-1]);
    }
    return final_A;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 12116 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 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 68 ms 12352 KB Output is correct
4 Correct 63 ms 4064 KB Output is correct
5 Correct 128 ms 15520 KB Output is correct
6 Correct 129 ms 15540 KB Output is correct
7 Correct 137 ms 15560 KB Output is correct
8 Correct 125 ms 15412 KB Output is correct
9 Correct 127 ms 15560 KB Output is correct

Subtask #5
0 / 33.0

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