oj.uz

Submission #492726

# Submission time Handle Problem Language Result Execution time Memory
492726 2021-12-08T14:05:53 Z lukameladze Distributing Candies (IOI21_candies) C++17
100 / 100
 2599 ms 58544 KB 
# include <bits/stdc++.h>
#include "candies.h"
#define f first
#define s second
#define pb push_back
#define pii pair <long long, long long> 
using namespace std;
const int N = 3e5 + 5;
long long n,q,l[N],r[N],val[N],idx,c[N],le,ri,mid,mxid,mnid,ans,cc1;
vector < pii > v[N];
long long lazy[4*N];
struct nd {
    long long mx;
    long long mn;
    long long mxidx;
    long long mnidx;
    long long sum;
};
nd tree[4*N],emp;
nd merge(nd a, nd b) {
    nd ans;
    ans.mx = max(a.mx,b.mx);
    ans.mn = min(a.mn,b.mn);
    if (a.mx >= b.mx) ans.mxidx = a.mxidx;
    else ans.mxidx = b.mxidx;
    if (a.mn <= b.mn) ans.mnidx = a.mnidx;
    else ans.mnidx = b.mnidx;
    ans.sum = a.sum + b.sum;
    return ans;
}
void build(int node, int le, int ri) {
    if (le == ri) {
        tree[node].mx = 0;
        tree[node].mn = 0;
        tree[node].mxidx = le;
        tree[node].mnidx = le;
        tree[node].sum = 0;
        return ;
    }
    int mid = (le + ri) / 2;
    build(2*node, le, mid);
    build(2*node + 1, mid + 1, ri);
    tree[node] = merge(tree[2*node],tree[2*node + 1]);
}
void update(int node, int le, int ri, int start, int end, long long val) {
    if (lazy[node]) {
        tree[node].mx += lazy[node];
        tree[node].mn += lazy[node];
        tree[node].sum += (ri - le + 1) * lazy[node];
        if (le != ri) {
            lazy[2*node] += lazy[node];
            lazy[2*node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if (le > end || ri < start) return ;
    if (le >= start && ri <= end) {
        tree[node].mx += val;
        tree[node].mn += val;
        tree[node].sum += (ri - le + 1) * val;
        if (le != ri) {
            lazy[2*node] += val;
            lazy[2*node + 1] += val; 
        }
        return ;
    }
    int mid = (le + ri) / 2;
    update(2*node, le, mid ,start,end,val);
    update(2*node + 1, mid + 1, ri, start,end, val);
    tree[node] = merge(tree[2*node],tree[2*node + 1]);
}
nd getans(int node, int le, int ri, int start, int end) {
    if (lazy[node]) {
        tree[node].mx += lazy[node];
        tree[node].mn += lazy[node];
        tree[node].sum += (ri - le + 1) * lazy[node];
        if (le != ri) {
            lazy[2*node] += lazy[node];
            lazy[2*node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if (le > end || ri < start) return emp;
    if (le >= start && ri <= end) {
        return tree[node];
    }
    int mid = (le + ri) / 2;
    return merge(getans(2*node,le,mid,start,end), getans(2*node + 1, mid + 1, ri, start,end));
}
int check(int mid) {
    if (getans(1,0,q,mid,q).mx - getans(1,0,q,mid,q).mn >= cc1) return 1;
    else return 0;
}
vector<int> distribute_candies(vector<int> cc, vector<int> ll, vector<int> rr, vector<int> vall) {
    n = cc.size();
	for (int i = 1; i <= n; i++) {
		c[i] = cc[i - 1];
	}
	emp.mx = -1e17;
	vector <int> anss;
	anss.clear();
	emp.mn = 1e17;
	emp.sum = 0;
	q = ll.size();
	for (int i = 1; i <= q; i++) {
		l[i] = ll[i - 1];
		r[i] = rr[i - 1];
		val[i] = vall[i - 1];
		l[i]++;
		r[i]++;
		v[l[i]].pb({i,val[i]});
		v[r[i] + 1].pb({i,-val[i]});
	}
	build(1,0,q);
	for (int i = 1; i <= n; i++) {
	    for (int j = 0; j < v[i].size(); j++) {
	        idx = v[i][j].f;
	        update(1,0,q,idx,q,v[i][j].s);
	    
	    }
	   le = 0; ri = q;
	   cc1 = c[i];
	   ans = -1;
	   while (le <= ri) {
	       mid = (le + ri) / 2;
	       if (check(mid)) {
	           ans = mid;
	           le = mid + 1;
	       } else ri = mid - 1;
	   }
	   if (ans == -1) {
	       if (getans(1,0,q,0,q).mn < 0) {
	           long long leeid = getans(1,0,q,0,q).mnidx;
	          anss.pb(getans(1,0,q,q,q).sum - getans(1,0,q,leeid,leeid).sum);
	           continue;
	       }
	       anss.pb(getans(1,0,q,q,q).sum);//<<endl;
	       continue;
	   }
	   long long mnval = getans(1,0,q,ans,q).mn;
	   mnid = getans(1,0,q,ans,q).mnidx;
	   long long mxval = getans(1,0,q,ans,q).mx;
	   mxid = getans(1,0,q,ans,q).mxidx;
	   if (mnid >= mxid) {
	       le = mnid;
	       ri = q;
	        //long long leeid = getans(1,0,q,mnid,q).mnidx;
	       anss.pb(getans(1,0,q,q,q).sum-getans(1,0,q,mnid,mnid).sum);//<<endl;
	   } else {
	       le = mxid;
	       ri = q;
	       //long long leeid = getans(1,0,q,mxid,q).mxidx;
	       anss.pb(c[i] + (getans(1,0,q,q,q).sum - getans(1,0,q,mxid,mxid).sum));//<<endl;
	   }
	}
	return anss;
}

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:116:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |      for (int j = 0; j < v[i].size(); j++) {
      |                      ~~^~~~~~~~~~~~~
candies.cpp:140:15: warning: unused variable 'mnval' [-Wunused-variable]
  140 |     long long mnval = getans(1,0,q,ans,q).mn;
      |               ^~~~~
candies.cpp:142:15: warning: unused variable 'mxval' [-Wunused-variable]
  142 |     long long mxval = getans(1,0,q,ans,q).mx;
      |               ^~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7668 KB Output is correct
4 Correct 7 ms 7748 KB Output is correct
5 Correct 15 ms 7852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2599 ms 56168 KB Output is correct
2 Correct 2508 ms 57832 KB Output is correct
3 Correct 2374 ms 57832 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 339 ms 51968 KB Output is correct
3 Correct 842 ms 15212 KB Output is correct
4 Correct 2520 ms 58544 KB Output is correct
5 Correct 2389 ms 58288 KB Output is correct
6 Correct 2462 ms 58320 KB Output is correct
7 Correct 2447 ms 58340 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 7 ms 7348 KB Output is correct
3 Correct 167 ms 49396 KB Output is correct
4 Correct 726 ms 13260 KB Output is correct
5 Correct 1977 ms 54220 KB Output is correct
6 Correct 2029 ms 54420 KB Output is correct
7 Correct 2051 ms 54300 KB Output is correct
8 Correct 1936 ms 54292 KB Output is correct
9 Correct 2032 ms 54384 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7668 KB Output is correct
4 Correct 7 ms 7748 KB Output is correct
5 Correct 15 ms 7852 KB Output is correct
6 Correct 2599 ms 56168 KB Output is correct
7 Correct 2508 ms 57832 KB Output is correct
8 Correct 2374 ms 57832 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 339 ms 51968 KB Output is correct
11 Correct 842 ms 15212 KB Output is correct
12 Correct 2520 ms 58544 KB Output is correct
13 Correct 2389 ms 58288 KB Output is correct
14 Correct 2462 ms 58320 KB Output is correct
15 Correct 2447 ms 58340 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 7 ms 7348 KB Output is correct
18 Correct 167 ms 49396 KB Output is correct
19 Correct 726 ms 13260 KB Output is correct
20 Correct 1977 ms 54220 KB Output is correct
21 Correct 2029 ms 54420 KB Output is correct
22 Correct 2051 ms 54300 KB Output is correct
23 Correct 1936 ms 54292 KB Output is correct
24 Correct 2032 ms 54384 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 733 ms 13396 KB Output is correct
27 Correct 369 ms 52424 KB Output is correct
28 Correct 2375 ms 58364 KB Output is correct
29 Correct 2449 ms 58384 KB Output is correct
30 Correct 2532 ms 58216 KB Output is correct
31 Correct 2445 ms 58292 KB Output is correct
32 Correct 2437 ms 58320 KB Output is correct