oj.uz

Submission #923477

# Submission time Handle Problem Language Result Execution time Memory
923477 2024-02-07T09:46:30 Z LIF Distributing Candies (IOI21_candies) C++17
38 / 100
 937 ms 55672 KB 
#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;
}

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: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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 16744 KB Output is correct
2 Correct 79 ms 20808 KB Output is correct
3 Correct 84 ms 20676 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 180 ms 9260 KB Output is correct
3 Correct 85 ms 51892 KB Output is correct
4 Correct 509 ms 55404 KB Output is correct
5 Correct 649 ms 55564 KB Output is correct
6 Correct 937 ms 55672 KB Output is correct
7 Correct 758 ms 55556 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 44 ms 9208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 96 ms 16744 KB Output is correct
7 Correct 79 ms 20808 KB Output is correct
8 Correct 84 ms 20676 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 180 ms 9260 KB Output is correct
11 Correct 85 ms 51892 KB Output is correct
12 Correct 509 ms 55404 KB Output is correct
13 Correct 649 ms 55564 KB Output is correct
14 Correct 937 ms 55672 KB Output is correct
15 Correct 758 ms 55556 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Incorrect 44 ms 9208 KB Output isn't correct
19 Halted 0 ms 0 KB -