제출 #481166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
481166		rumen_m	사탕 분배 (IOI21_candies)	C++17	100 / 100	419 ms	74632 KiB

candies

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33