답안 #923470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923470 2024-02-07T09:33:46 Z LIF 사탕 분배 (IOI21_candies) C++17
27 / 100
922 ms 53896 KB
#include "candies.h"
#include<bits/stdc++.h>
#include <vector>
#define INF 1e18+7
using namespace std;
long long int n,m;
long long 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;
vector<int> distribute_candies(vector<int> c,vector<int> ll,vector<int> rr,vector<int> vv) 
{
    n = c.size();
    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;
}

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:181:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for(int i=0;i<ll.size();i++)
      |                 ~^~~~~~~~~~
candies.cpp:185:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int i=0;i<ll.size();i++)
      |                 ~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 654 ms 53704 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 207 ms 9208 KB Output is correct
3 Correct 86 ms 49996 KB Output is correct
4 Correct 502 ms 53680 KB Output is correct
5 Correct 643 ms 53692 KB Output is correct
6 Correct 922 ms 53896 KB Output is correct
7 Correct 748 ms 53676 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -