oj.uz

Submission #494011

# Submission time Handle Problem Language Result Execution time Memory
494011 2021-12-13T18:01:37 Z wildturtle Distributing Candies (IOI21_candies) C++17
100 / 100
 2363 ms 59112 KB 
# 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=-1;
		while(le<=ri) {
			mid=(le+ri)/2;
			if(go(mid)) { le=mid+1; ans=mid; }
			else ri=mid-1;
		}
		if(ans==-1) {
		    if(get(1,0,q,0,q).mn<0) {
		        idx=get(1,0,q,0,q).mnidx;
		        vans.pb(get(1,0,q,q,q).sum-get(1,0,q,idx,idx).sum);
		        continue;
		    }
		    vans.pb(get(1,0,q,q,q).sum);
		    continue;
		}
		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

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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 5324 KB Output is correct
4 Correct 6 ms 5404 KB Output is correct
5 Correct 12 ms 5400 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2341 ms 54448 KB Output is correct
2 Correct 2304 ms 58088 KB Output is correct
3 Correct 2301 ms 57628 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 365 ms 50924 KB Output is correct
3 Correct 729 ms 13620 KB Output is correct
4 Correct 2236 ms 59100 KB Output is correct
5 Correct 2248 ms 58916 KB Output is correct
6 Correct 2246 ms 58856 KB Output is correct
7 Correct 2348 ms 59052 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 139 ms 48108 KB Output is correct
4 Correct 694 ms 11516 KB Output is correct
5 Correct 1876 ms 53936 KB Output is correct
6 Correct 1825 ms 54696 KB Output is correct
7 Correct 1895 ms 54960 KB Output is correct
8 Correct 1837 ms 53756 KB Output is correct
9 Correct 1958 ms 55020 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 5324 KB Output is correct
4 Correct 6 ms 5404 KB Output is correct
5 Correct 12 ms 5400 KB Output is correct
6 Correct 2341 ms 54448 KB Output is correct
7 Correct 2304 ms 58088 KB Output is correct
8 Correct 2301 ms 57628 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 365 ms 50924 KB Output is correct
11 Correct 729 ms 13620 KB Output is correct
12 Correct 2236 ms 59100 KB Output is correct
13 Correct 2248 ms 58916 KB Output is correct
14 Correct 2246 ms 58856 KB Output is correct
15 Correct 2348 ms 59052 KB Output is correct
16 Correct 2 ms 4940 KB Output is correct
17 Correct 3 ms 5052 KB Output is correct
18 Correct 139 ms 48108 KB Output is correct
19 Correct 694 ms 11516 KB Output is correct
20 Correct 1876 ms 53936 KB Output is correct
21 Correct 1825 ms 54696 KB Output is correct
22 Correct 1895 ms 54960 KB Output is correct
23 Correct 1837 ms 53756 KB Output is correct
24 Correct 1958 ms 55020 KB Output is correct
25 Correct 2 ms 4940 KB Output is correct
26 Correct 678 ms 11496 KB Output is correct
27 Correct 310 ms 50472 KB Output is correct
28 Correct 2244 ms 58920 KB Output is correct
29 Correct 2252 ms 58980 KB Output is correct
30 Correct 2363 ms 59048 KB Output is correct
31 Correct 2234 ms 59052 KB Output is correct
32 Correct 2257 ms 59112 KB Output is correct