oj.uz

Submission #628030

# Submission time Handle Problem Language Result Execution time Memory
628030 2022-08-13T03:38:31 Z truc12a2cvp Distributing Candies (IOI21_candies) C++17
29 / 100
 122 ms 17316 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int N = 2e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
/*
//subtask 3
struct F{
       int L, R, sum;
       F(int _L = 0, int _R = 0, int _sum = 0) : L(_L), R(_R), sum(_sum) {}
       F operator + (const F& op) const{
              return F(max(op.L, min(op.R, L + op.sum)),
                       max(op.L, min(op.R, R + op.sum)),
                       sum + op.sum);
       }
};

int C;

struct ST_lazy{
       int n;
       vector<F> ST;
       ST_lazy(int _n = 0){
              n = _n;
              ST.resize(4 * n + 5);
       }
       void down(int id, int l, int r){
              if(l == r) return;
              ST[id * 2] = ST[id * 2] + ST[id];
              ST[id * 2 + 1] = ST[id * 2 + 1] + ST[id];
              ST[id] = F(0, C, 0);
       }
       void update(int id, int l, int r, int u, int v, int add){
              down(id, l, r);
              if(r < u || v < l) return;
              if(u <= l && r <= v){
                     ST[id] = ST[id] + F(0, C, add);
                     return;
              }
              int mid = l + r >> 1;
              update(id * 2, l, mid, u, v, add);
              update(id * 2 + 1, mid + 1, r, u, v, add);
       }
       int get(int id, int l, int r, int i){
              down(id, l, r);
              if(l == r) return max(ST[id].L, min(ST[id].R, ST[id].sum));
              int mid = l + r >> 1;
              if(i <= mid) return get(id * 2, l, mid, i);
              return get(id * 2 + 1, mid + 1, r, i);
       }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
       int n = c.size(), q = l.size();
       ST_lazy ST(n);
       C = c[0];
       for(int i = 0; i < q; i ++){
              ST.update(1, 1, n, l[i] + 1, r[i] + 1, v[i]);
       }
       vector<int> ans;
       for(int i = 1; i <= n; i ++) ans.push_back(ST.get(1, 1, n, i));
       return ans;
}
*/

int n;
ll suf_min[N], suf_max[N], sum[N];

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
       n = v.size();
       for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + v[i - 1];
       suf_max[n] = suf_min[n] = sum[n];
       for(int i = n - 1; i >= 0; i --){
              suf_max[i] = max(suf_max[i + 1], sum[i]);
              suf_min[i] = min(suf_min[i + 1], sum[i]);
       }
       vector<int> res;
       for(int i = 0; i < (int)c.size(); i ++){
              int pos = 0, l = 1, r = n;
              while(l <= r){
                    int mid = l + r >> 1;
                    if(suf_max[mid] - suf_min[mid] > c[i]) pos = mid, l = mid + 1;
                    else r = mid - 1;
              }
              if(suf_max[pos] - sum[pos] > c[i]) res.push_back(c[i] - (suf_max[pos] - sum[n]));
              else res.push_back(sum[n] - suf_min[pos]);
       }
       return res;
}
/*
int main(){
       vector<int> res = distribute_candies({10, 15, 100}, {1, 1, 1}, {3, 3, 3}, {10, 6, -13});
       for(int x : res) cout << x << " ";
}
*/

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:83:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |                     int mid = l + r >> 1;
      |                               ~~^~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 17244 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 340 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 49 ms 12240 KB Output is correct
4 Correct 47 ms 4264 KB Output is correct
5 Correct 98 ms 15828 KB Output is correct
6 Correct 122 ms 16604 KB Output is correct
7 Correct 102 ms 17092 KB Output is correct
8 Correct 97 ms 15832 KB Output is correct
9 Correct 105 ms 17316 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 308 KB Output isn't correct
3 Halted 0 ms 0 KB -