oj.uz

Submission #481166

# Submission time Handle Problem Language Result Execution time Memory
481166 2021-10-19T16:40:22 Z rumen_m Distributing Candies (IOI21_candies) C++17
100 / 100
 419 ms 74632 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 2e6+2;

vector <int> ans;
long long MIN(long long a, long long b)
{
    if(a<b)return a;
    return b;
}
long long MAX(long long a, long long b)
{
    if(a>b)return a;
    return b;
}
struct Segment
{
   long long sum[MAXN],mn[MAXN],mx[MAXN];
   void update(int v, int from, int to, int t, int delta)
   {
       if(from==to)
       {
           sum[v]+=delta;
           mn[v] = sum[v];
           mx[v] = sum[v];
           return ;
       }
       int mid = (from+to)/2;
       if(t<=mid)update(2*v,from,mid,t,delta);
       else
        update(2*v+1,mid+1,to,t,delta);
       sum[v] = sum[2*v] + sum[2*v+1];
       mn[v] = MIN(mn[2*v],sum[2*v]+mn[2*v+1]);
       mx[v] = MAX(mx[2*v],sum[2*v]+mx[2*v+1]);
       return ;
   }
   int query(int v, int from, int to, int c)
   {
      // cout<<v<<" "<<from<<" "<<to<<" "<<c<<" "<<sum[v]<<" "<<mn[v]<<" "<<mx[v]<<endl;
       if(from==to)return MAX(0,MIN(sum[v],c));
       int mid = (from+to)/2;
       if(mx[2*v+1] - mn[2*v+1] > c)return query(2*v+1, mid+1, to, c);
       int curr = query(2*v,from,mid,c);
      // cout<<curr<<" "<<mn[2*v+1]<<" "<<sum[2*v+1]<<endl;
       if(curr + mx[2*v+1] > c) return (c - (mx[2*v+1]-sum[2*v+1]));
       if(curr + mn[2*v+1] < 0) return (sum[2*v+1]-mn[2*v+1]);

       return curr + sum[2*v+1];
   }
};
Segment S;
vector <pair <int,int> > curr[MAXN];
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();
    int i,j;
    int q = l.size();
  for(i=0;i<q;i++)
  {
      curr[l[i]].push_back({i,v[i]});
      curr[r[i]+1].push_back({i,-v[i]});
  }
  ans.resize(n);
  for(i=0;i<n;i++)
  {

      for(auto p : curr[i])
      {
          S.update(1,0,q-1,p.first,p.second);
      }
      ans[i] = S.query(1,0,q-1,c[i]);// cout<<"OK"<<endl;
  }
    return ans;
}

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:57:11: warning: unused variable 'j' [-Wunused-variable]
   57 |     int i,j;
      |           ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47196 KB Output is correct
2 Correct 29 ms 47264 KB Output is correct
3 Correct 33 ms 47436 KB Output is correct
4 Correct 31 ms 47448 KB Output is correct
5 Correct 34 ms 47476 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 74496 KB Output is correct
2 Correct 395 ms 74392 KB Output is correct
3 Correct 378 ms 74436 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47180 KB Output is correct
2 Correct 224 ms 68680 KB Output is correct
3 Correct 101 ms 51740 KB Output is correct
4 Correct 373 ms 74452 KB Output is correct
5 Correct 399 ms 74452 KB Output is correct
6 Correct 404 ms 74552 KB Output is correct
7 Correct 399 ms 74508 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47312 KB Output is correct
2 Correct 30 ms 47248 KB Output is correct
3 Correct 122 ms 67564 KB Output is correct
4 Correct 92 ms 50796 KB Output is correct
5 Correct 182 ms 70556 KB Output is correct
6 Correct 185 ms 70568 KB Output is correct
7 Correct 190 ms 70564 KB Output is correct
8 Correct 192 ms 70516 KB Output is correct
9 Correct 197 ms 70564 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47196 KB Output is correct
2 Correct 29 ms 47264 KB Output is correct
3 Correct 33 ms 47436 KB Output is correct
4 Correct 31 ms 47448 KB Output is correct
5 Correct 34 ms 47476 KB Output is correct
6 Correct 416 ms 74496 KB Output is correct
7 Correct 395 ms 74392 KB Output is correct
8 Correct 378 ms 74436 KB Output is correct
9 Correct 32 ms 47180 KB Output is correct
10 Correct 224 ms 68680 KB Output is correct
11 Correct 101 ms 51740 KB Output is correct
12 Correct 373 ms 74452 KB Output is correct
13 Correct 399 ms 74452 KB Output is correct
14 Correct 404 ms 74552 KB Output is correct
15 Correct 399 ms 74508 KB Output is correct
16 Correct 32 ms 47312 KB Output is correct
17 Correct 30 ms 47248 KB Output is correct
18 Correct 122 ms 67564 KB Output is correct
19 Correct 92 ms 50796 KB Output is correct
20 Correct 182 ms 70556 KB Output is correct
21 Correct 185 ms 70568 KB Output is correct
22 Correct 190 ms 70564 KB Output is correct
23 Correct 192 ms 70516 KB Output is correct
24 Correct 197 ms 70564 KB Output is correct
25 Correct 31 ms 47248 KB Output is correct
26 Correct 93 ms 50628 KB Output is correct
27 Correct 222 ms 68692 KB Output is correct
28 Correct 385 ms 74632 KB Output is correct
29 Correct 378 ms 74420 KB Output is correct
30 Correct 419 ms 74456 KB Output is correct
31 Correct 374 ms 74440 KB Output is correct
32 Correct 398 ms 74436 KB Output is correct