제출 #923477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
923477		LIF	사탕 분배 (IOI21_candies)	C++17	38 / 100	937 ms	55672 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
#include <vector>
#define INF 1e18+7
using namespace std;
long long int n,m;
int a[2000005];
long long int capacity[2000005];
struct node
{
	//tmx : tag maximum ; similar to define tmn , tad;
	//cmx : the count of maximum; similar to define cmn; it is used to calculate the sum.
	//mx2 : the second maximum;
	long long int mx,mx2,mn,mn2,cmx,cmn,tmx,tmn,tad;
	long long int sum;
}t[2000005];
void pushup(int u)
{
	int lu = u * 2;int ru = u*2+1;
	t[u].sum = t[lu].sum + t[ru].sum;
	if(t[lu].mx == t[ru].mx)
	{
		t[u].mx = t[lu].mx;t[u].cmx = t[lu].cmx + t[ru].cmx;
		t[u].mx2 = max(t[lu].mx2,t[ru].mx2);
	}
	if(t[lu].mx > t[ru].mx)
	{
		t[u].mx = t[lu].mx;t[u].cmx = t[lu].cmx;
		t[u].mx2 = max(t[lu].mx2,t[ru].mx);
	}
	if(t[lu].mx < t[ru].mx)
	{
		t[u].mx = t[ru].mx;t[u].cmx = t[ru].cmx;
		t[u].mx2 = max(t[ru].mx2,t[lu].mx);
	}
	if(t[lu].mn == t[ru].mn)
	{
		t[u].mn = t[lu].mn;t[u].cmn = t[lu].cmn + t[ru].cmn;
		t[u].mn2 = min(t[lu].mn2,t[ru].mn2);
	}
	if(t[lu].mn < t[ru].mn)
	{
		t[u].mn = t[lu].mn;t[u].cmn = t[lu].cmn;
		t[u].mn2 = min(t[lu].mn2,t[ru].mn);
	}
	if(t[lu].mn > t[ru].mn)
	{
		t[u].mn = t[ru].mn;t[u].cmn = t[ru].cmn;
		t[u].mn2 = min(t[ru].mn2,t[lu].mn);
	}
    return;
}
void push_add(int nownode,long long int l,long long int r,long long int v)
{
    // this function is for update the value of nownode[l,r];
    t[nownode].sum += (long long)((r-l+1)) * v;
    t[nownode].mx += v;t[nownode].mn += v;
    if(t[nownode].mx2 != -INF)t[nownode].mx2 += v;
    if(t[nownode].mn2 != INF)t[nownode].mn2 += v;
    if(t[nownode].tmx != -INF)t[nownode].tmx += v;
    if(t[nownode].tmn != INF)t[nownode].tmn += v;
    t[nownode].tad += v;
    return;
}
void push_min(int nownode, long long int tag)
{
    //we should do the following things: if nownode.mx <= tag , return; otherwise update it .
    // this function is for update the tmn of nownode.
    if(t[nownode].mx <= tag)return;
    t[nownode].sum += (long long)(tag - t[nownode].mx) * t[nownode].cmx;
    if(t[nownode].mn2 == t[nownode].mx)t[nownode].mn2 = tag;
    if(t[nownode].mn == t[nownode].mx)t[nownode].mn = tag;
    if(t[nownode].tmx > tag)t[nownode].tmx = tag;
    t[nownode].mx = tag;t[nownode].tmn = tag;
    return;
}
void push_max(int nownode,long long int tag)
{
    if(t[nownode].mn > tag)return;
    t[nownode].sum += (long long)(tag-t[nownode].mn) * t[nownode].cmn;
    if(t[nownode].mx2 == t[nownode].mn)t[nownode].mx2 = tag;
    if(t[nownode].mx == t[nownode].mn)t[nownode].mx = tag;
    if(t[nownode].tmn < tag)t[nownode].tmn = tag;
    t[nownode].mn = tag;t[nownode].tmx = tag;
    return;
}
void pushdown(int u,int l,int r)
{
    int lu = u*2;int ru = u*2+1;int mid = (l+r)>>1;
    if(t[u].tad != 0)
    {
        push_add(lu,l,mid,t[u].tad);
        push_add(ru,mid+1,r,t[u].tad);
    }
    if(t[u].tmx != -INF)push_max(lu,t[u].tmx),push_max(ru,t[u].tmx);
    if(t[u].tmn != INF)push_min(lu,t[u].tmn),push_min(ru,t[u].tmn);
    t[u].tad = 0;t[u].tmx = -INF;t[u].tmn = INF;
    return;
}
void build(int nownode,int l,int r)
{
	t[nownode].tmn = INF; t[nownode].tmx = -INF;
	if(l == r)
	{
		t[nownode].sum = t[nownode].mx = t[nownode].mn = a[l];
		t[nownode].mx2 = -INF;t[nownode].mn2 = INF;
		t[nownode].cmx = t[nownode].cmn = 1;
		return;
	}
	int mid = (l+r)>>1;
	build(nownode*2 ,l,mid);build(nownode*2+1, mid+1 , r);
	pushup(nownode);
    return;
}
void add(int L,int R,int v,int u,int l,int r)
{
    // l -> nowl , r -> nowr;
    if(R < l || r < L)return;
    if(L <= l && r <= R)
    {
        push_add(u,l,r,v);return;
    }
    int mid = (l+r)>>1;
    pushdown(u,l,r);
    add(L,R,v,u*2,l,mid);
    add(L,R,v,u*2+1,mid+1,r);
    pushup(u);
    return;
}
long long int qsum(int L,int R,int u,int l,int r)
{
    if(R < l || r < L)return 0;
    if(L <= l && r <= R)return t[u].sum;
    int mid = (l+r)>>1;
    pushdown(u,l,r);
    long long int ans = 0;
    ans += (qsum(L,R,u*2,l,mid) + qsum(L,R,u*2+1,mid+1,r));
    return ans;
}
void tomin(int L,int R,int v,int u,int l,int r)
{
    //there are 3 situation for getting minimum:
    //first , if nownode.mx <= v, it is no use for this operation,return;
    //second, if second max < t <= max , we can operate this node directly.
    //last , if t <= second max , we don't know how many number, we need recursion more.
    if(R < l || r < L || t[u].mx <= v)return;
    if(L <= l && r <= R && t[u].mx2 < v)
    {
        push_min(u,v);
        return;
    }
    int mid = (l+r)>>1;
    pushdown(u,l,r);
    tomin(L,R,v,u*2,l,mid);
    tomin(L,R,v,u*2+1,mid+1,r);
    pushup(u);
    return;
}
void tomax(int L,int R,int v,int u,int l,int r)
{
    if(R < l || r < L || t[u].mn >= v)return;
    if(L <= l && r <= R && t[u].mn2 > v)
    {
        push_max(u,v);
        return;
    }
    int mid = (l+r)>>1;
    pushdown(u,l,r);
    tomax(L,R,v,u*2,l,mid);
    tomax(L,R,v,u*2+1,mid+1,r);
    pushup(u);
    return;
}
vector<int> rpp;
long long int b[500005];
long long int su[500005];
vector<int> distribute_candies(vector<int> c,vector<int> ll,vector<int> rr,vector<int> vv) 
{
	
    n = c.size();
    if(n <= 2000 && ll.size() <= 2000)
    {
    	for(int i=0;i<=n-1;i++)a[i] = 0;
    	for(int i=0;i<ll.size();i++)
    	{
    		int xx = ll[i];
    		int yy = rr[i];
    		for(int j=xx;j<=yy;j++)
    		{
    			a[j] += vv[i];
    			a[j] = min(c[j],a[j]);
    			a[j] = max(0,a[j]);
			}
		}
		for(int i=0;i<n;i++)
		{
			rpp.push_back(a[i]);
		}
		return rpp;
	}
	bool flag = true;
	for(int i=0;i<vv.size();i++)
	{
		if(vv[i] <= 0)flag = false;
	}
	if(flag == true)
	{
		for(int i=0;i<vv.size();i++)
		{
			b[ll[i]] += vv[i];
			b[rr[i]+1] -= vv[i];
		}
		long long int temp = 0;
		for(int i=0;i<n;i++)
		{
			temp += b[i];
			su[i] = temp;
		}
		for(int i=0;i<n;i++)
		{
			su[i] = min((long long)c[i],su[i]);
		}
		for(int i=0;i<n;i++)rpp.push_back(su[i]);
		return rpp;
	}
    int k = c[0];
    for(int i=1;i<=n;i++)a[i] = 0;
    build(1,1,n);
    for(int i=0;i<ll.size();i++)
    {
        ll[i] += 1;rr[i] += 1;
    }
    for(int i=0;i<ll.size();i++)
    {
        add(ll[i],rr[i],vv[i],1,1,n);
        tomin(1,n,k,1,1,n);
        tomax(1,n,0,1,1,n);
    }
    for(int i=1;i<=n;i++)
    {
        long long int xx = qsum(i,i,1,1,n);
        rpp.push_back(xx);
    }
    return rpp;
}

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

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:184:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |      for(int i=0;i<ll.size();i++)
      |                  ~^~~~~~~~~~
candies.cpp:202:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |  for(int i=0;i<vv.size();i++)
      |              ~^~~~~~~~~~
candies.cpp:208:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |   for(int i=0;i<vv.size();i++)
      |               ~^~~~~~~~~~
candies.cpp:229:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for(int i=0;i<ll.size();i++)
      |                 ~^~~~~~~~~~
candies.cpp:233:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |     for(int i=0;i<ll.size();i++)
      |                 ~^~~~~~~~~~

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