oj.uz

Submission #828739

# Submission time Handle Problem Language Result Execution time Memory
828739 2023-08-17T14:44:37 Z fatemetmhr Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 10864 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,O3")

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair

const int ss    = 1500;
const int maxn5 = 2e5 + 10;

int ret[maxn5], c[maxn5], sig[maxn5];
int L[maxn5], R[maxn5], V[maxn5];

std::vector<int> distribute_candies(std::vector<int> C, std::vector<int> LL,
                                    std::vector<int> RR, std::vector<int> VV) {
    int n = C.size(), q = LL.size();
    for(int i = 0; i < n; i++)
        c[i] = C[i];
    for(int i = 0; i < q; i++){
        L[i] = LL[i];
        R[i] = RR[i];
        V[i] = VV[i];
        sig[i] = (V[i] > 0 ? 1 : -1);
    }
    for(int tt = 0; tt < n; tt += ss){
        for(int i = 1; i < q; i += 2){
            int lim = MIN(tt + ss, n);
            int v1 = V[i - 1], v2 = V[i];
            if(MAX(L[i], L[i - 1] > tt || MIN(R[i], R[i - 1]) < lim - 1)){
                int l = MAX(tt, L[i - 1]), r = MIN(lim, R[i - 1] + 1);
                for(int j = l; j < r; j++){
                    ret[j] += v1;
                    ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                }
                l = MAX(tt, L[i]); 
                r = MIN(lim, R[i] + 1);
                for(int j = l; j < r; j++){
                    ret[j] += v2;
                    ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                }
            }
            else{
                if(sig[i] == sig[i - 1]){
                    v1 += v2;
                    if(v1 > 0){
                        for(int i = tt; i < lim; i++){
                            ret[i] = MIN(c[i], ret[i] + v1);
                        }
                    }
                    else{
                        for(int i = tt; i < lim; i++){
                            ret[i] = MAX(0, ret[i] + v1);
                        }
                    }
                }
                else{
                    for(int j = tt; j < lim; j++){
                        ret[j] += v1;
                        ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                        ret[j] += v2;
                        ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                    }
                }
            }
        }
    }
    if(q & 1){
        for(int i = L[q - 1]; i <= R[q - 1]; i++){
            ret[i] += V[q - 1];
            ret[i] = (ret[i] < 0 ? 0 : (ret[i] > c[i] ? c[i] : ret[i]));
        }
    }

    std::vector<int> s;
    for(int i = 0; i < n; i++)
        s.pb(ret[i]);
    return s;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5053 ms 10740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 151 ms 8172 KB Output is correct
3 Correct 183 ms 5544 KB Output is correct
4 Execution timed out 5085 ms 10864 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
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 349 ms 8176 KB Output is correct
4 Correct 354 ms 4676 KB Output is correct
5 Execution timed out 5059 ms 10796 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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