Submission #831071

#	Time	Username	Problem	Language	Result	Execution time	Memory
831071		fatemetmhr	Distributing Candies (IOI21_candies)	C++17	100 / 100	2876 ms	12644 KiB

candies

//#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    = 2000;
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);
            if(MAX(L[i], L[i - 1] > tt || MIN(R[i], R[i - 1]) < lim - 1)){
                int v1 = V[i - 1], v2 = V[i];
                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]){
                    if(sig[i] == 1){
                        unsigned v = V[i - 1] + V[i];
                        for(int i = tt; i < lim; i++){
                            ret[i] = MIN(c[i], unsigned(ret[i]) + v);
                        }
                    }
                    else{
                        int v = V[i - 1] + V[i];
                        for(int i = tt; i < lim; i++){
                            ret[i] = MAX(0, ret[i] + v);
                        }
                    }
                }
                else{
                    int v1 = V[i - 1], v2 = V[i];
                    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;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:15:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   15 | #define MIN(x, y) ((x) < (y) ? (x) : (y))
      |                    ~~~~^~~~~
candies.cpp:60:38: note: in expansion of macro 'MIN'
   60 |                             ret[i] = MIN(c[i], unsigned(ret[i]) + v);
      |                                      ^~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33