Submission #494009

#	Time	Username	Problem	Language	Result	Execution time	Memory
494009		wildturtle	Distributing Candies (IOI21_candies)	C++17	0 / 100	2292 ms	55512 KiB

candies

# include <bits/stdc++.h>
#include "candies.h"
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
const int N=2e5+5;
ll n,q,le,ri,mid,ans,c,idx,idx1;
ll C[N],cc[N],lz[4*N],L[N],R[N],V[N];
vector <int> vans;
vector < pair <ll,ll> > v[N];
struct nd {
	ll mx;
	ll mn; 
	ll sum;
	ll mxidx;
	ll mnidx;
};
nd ndd,tree[4*N];
nd merge(nd x,nd y) {
	nd mr;
	mr.mx=max(x.mx,y.mx);
	mr.mn=min(x.mn,y.mn);
	mr.sum=x.sum+y.sum;
	if(x.mx>=y.mx) mr.mxidx=x.mxidx;
	else mr.mxidx=y.mxidx;
	if(x.mn<=y.mn) mr.mnidx=x.mnidx;
	else mr.mnidx=y.mnidx;
	return mr;
}
void build(ll node,ll le,ll ri) {
	if(le==ri) {
		tree[node].mx=0;
		tree[node].mn=0;
		tree[node].sum=0;
		tree[node].mxidx=le;
		tree[node].mnidx=le;
		return;
	}
	build(2*node,le,(le+ri)/2);
	build(2*node+1,(le+ri)/2+1,ri);
	tree[node]=merge(tree[2*node],tree[2*node+1]);
}
void update(ll node,ll le,ll ri,ll start,ll end,ll val) {
	if(lz[node]) {
		tree[node].mx+=lz[node];
		tree[node].mn+=lz[node];
		tree[node].sum+=lz[node]*(ri-le+1);
		if(le!=ri) {
			lz[2*node]+=lz[node];
			lz[2*node+1]+=lz[node];
		}
		lz[node]=0;
	}
	if(ri<start || le>end) return;
	if(start<=le && ri<=end) {
		tree[node].mx+=val;
		tree[node].mn+=val;
		tree[node].sum+=val*(ri-le+1);
		if(le!=ri) {
			lz[2*node]+=val;
			lz[2*node+1]+=val;
		}
		return;
	}
	update(2*node,le,(le+ri)/2,start,end,val);
	update(2*node+1,(le+ri)/2+1,ri,start,end,val);
	tree[node]=merge(tree[2*node],tree[2*node+1]);
}
nd get(ll node,ll le,ll ri,ll start,ll end) {
	if(lz[node]) {
		tree[node].mx+=lz[node];
		tree[node].mn+=lz[node];
		tree[node].sum+=lz[node]*(ri-le+1);
		if(le!=ri) {
			lz[2*node]+=lz[node];
			lz[2*node+1]+=lz[node];
		}
		lz[node]=0;
	}
	if(le>end || ri<start) return ndd;
	if(start<=le && ri<=end) {
	    return tree[node];
	}
	return merge(get(2*node,le,(le+ri)/2,start,end),get(2*node+1,(le+ri)/2+1,ri,start,end));
}
bool go(ll x) {
	if(get(1,0,q,x,q).mx-get(1,0,q,x,q).mn>=c) return 1;
	else return 0;
}
vector<int> distribute_candies(vector<int> cc, vector<int> lll, vector<int> rr, vector<int> vall) {
	n=cc.size(); q=lll.size();
	ndd.mx=-1e18;
	ndd.mn=1e18;
	for(ll i=0;i<n;i++) {
		C[i+1]=cc[i];
	}
	for(ll i=0;i<q;i++) {
		L[i+1]=lll[i]+1;
		R[i+1]=rr[i]+1;
		V[i+1]=vall[i];
	}
	for(ll i=1;i<=q;i++) {
		v[L[i]].pb({i,V[i]});
		v[R[i]+1].pb({i,-V[i]});
	}
	build(1,0,q);
	for(ll i=1;i<=n;i++) {
		for(ll j=0;j<v[i].size();j++){
			update(1,0,q,v[i][j].f,q,v[i][j].sc);
		}
		c=C[i];
		le=0; ri=q; ans=0;
		while(le<=ri) {
			mid=(le+ri)/2;
			if(go(mid)) { le=mid+1; ans=mid; }
			else ri=mid-1;
		}
		idx=get(1,0,q,ans,q).mnidx;
		idx1=get(1,0,q,ans,q).mxidx;
		//cout<<ans<<" "<<idx<<" "<<idx1<<endl;
		if(idx>=idx1) {
			vans.pb(get(1,0,q,q,q).sum-get(1,0,q,idx,idx).sum);
		} else {
			vans.pb(c+get(1,0,q,q,q).sum-get(1,0,q,idx1,idx1).sum);
		}
	}
	return vans;
}/*
int main() {
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        assert(scanf("%d", &c[i]) == 1);
    }

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

    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;
}*/

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:110:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(ll j=0;j<v[i].size();j++){
      |              ~^~~~~~~~~~~~

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