oj.uz

Submission #437087

# Submission time Handle Problem Language Result Execution time Memory
437087 2021-06-25T18:49:47 Z nadidadit Distributing Candies (IOI21_candies) C++17
8 / 100
 269 ms 14896 KB 
#include "candies.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll cnt=0,cnt1=0,cnt2=0;
vector<ll>change;
ll mx=(ll)1e9+40;
void query(ll at,ll pos,ll l,ll r)
{
//	cout<<"l= "<<l<<" r= "<<r<<endl;
	if(pos<l || pos>r)
	{
		return;
	}
	if(pos>=l && pos<=r)
	{
		if(cnt<mx)
		{
		cnt+=change[at];
	    }
	    if(l==r)
	    {
	    	return;
		}
	//	cout<<"l= "<<l<<" r= "<<r<<" cnt= "<<cnt<<endl;
	}
	if(l==r)
	{
		return;
	}
	ll mid=(l+r)/2;
	query(at*2,pos,l,mid);
	query(at*2+1,pos,mid+1,r);
}
void update(ll at,ll L,ll R,ll l,ll r,ll u)
{
	cnt1++;
//	cout<<"at= "<<at<<" L= "<<L<<" R= "<<R<<" l= "<<l<<" r= "<<r<<endl;
	if(R<l || L>r)
	{
	//	cout<<"Hi"<<endl;
		return;
	}
//	cout<<"at= "<<at<<" L= "<<L<<" R= "<<R<<" l= "<<l<<" r= "<<r<<endl;
	if(l<=L && R<=r)
	{
	//	cout<<"L= "<<L<<" R= "<<R<<endl;
	    if(change[at]<mx)
	    {
			change[at]+=u;
	    }
		return;
	}
	if(L==R)
	{
		return;
	}
//	cout<<"Here"<<endl;
	ll mid=(L+R)/2;
	update(at*2,L,mid,l,r,u);
	update(at*2+1,mid+1,R,l,r,u);
}
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();
	for(ll i=0;i<4*n+50;i++)
	{
		change.push_back((ll)0);
	}
    std::vector<int> s(n);
    ll x=l.size();
    for(ll i=0;i<n;i++)
    {
    	s[i]=0;
	}
//	cout<<"Hello"<<endl;
	for(ll i=0;i<x;i++)
	{
		cnt1=0;
//		cout<<"i= "<<i<<" l= "<<l[i]+1<<" r= "<<r[i]+1<<endl;
		update(1,1,n,l[i]+1,r[i]+1,v[i]);
//		cout<<"cnt1= "<<cnt1<<endl;
	}
	for(ll i=0;i<n;i++)
	{
		cnt=0;
		cnt2=0;
	//	cout<<"i= "<<i<<endl;
		query(1,i+1,1,n);
		//cout<<"cnt2= "<<cnt2<<endl;
		s[i]=min((ll)cnt,(ll)c[i]);
	}
    return s;
}
/*int main() {
	freopen("inputin.txt","r",stdin);
	freopen("testoutput.txt","w",stdout);
//	cout<<"Hi"<<endl;
    int n;
    cin>>n;
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        cin>>c[i];
    }

    int q;
    cin>>q;
    std::vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        scanf("%d %d %d", &l[i], &r[i], &v[i]);
    }

    std::vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}
*/

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 14792 KB Output is correct
2 Correct 238 ms 14796 KB Output is correct
3 Correct 243 ms 14896 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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