oj.uz

Submission #492671

# Submission time Handle Problem Language Result Execution time Memory
492671 2021-12-08T11:04:43 Z lukameladze Distributing Candies (IOI21_candies) C++17
100 / 100
 2514 ms 62832 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,leeid,leeid).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,leeid,leeid).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 4 ms 7372 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 6 ms 7756 KB Output is correct
5 Correct 15 ms 7756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2493 ms 56064 KB Output is correct
2 Correct 2510 ms 56288 KB Output is correct
3 Correct 2478 ms 56148 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 337 ms 50292 KB Output is correct
3 Correct 881 ms 15124 KB Output is correct
4 Correct 2309 ms 62072 KB Output is correct
5 Correct 2478 ms 62456 KB Output is correct
6 Correct 2483 ms 62832 KB Output is correct
7 Correct 2394 ms 62192 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 6 ms 7372 KB Output is correct
3 Correct 147 ms 47844 KB Output is correct
4 Correct 761 ms 11948 KB Output is correct
5 Correct 1942 ms 52568 KB Output is correct
6 Correct 2001 ms 52676 KB Output is correct
7 Correct 2150 ms 52532 KB Output is correct
8 Correct 1988 ms 52568 KB Output is correct
9 Correct 2079 ms 52568 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 4 ms 7372 KB Output is correct
3 Correct 5 ms 7756 KB Output is correct
4 Correct 6 ms 7756 KB Output is correct
5 Correct 15 ms 7756 KB Output is correct
6 Correct 2493 ms 56064 KB Output is correct
7 Correct 2510 ms 56288 KB Output is correct
8 Correct 2478 ms 56148 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 337 ms 50292 KB Output is correct
11 Correct 881 ms 15124 KB Output is correct
12 Correct 2309 ms 62072 KB Output is correct
13 Correct 2478 ms 62456 KB Output is correct
14 Correct 2483 ms 62832 KB Output is correct
15 Correct 2394 ms 62192 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 6 ms 7372 KB Output is correct
18 Correct 147 ms 47844 KB Output is correct
19 Correct 761 ms 11948 KB Output is correct
20 Correct 1942 ms 52568 KB Output is correct
21 Correct 2001 ms 52676 KB Output is correct
22 Correct 2150 ms 52532 KB Output is correct
23 Correct 1988 ms 52568 KB Output is correct
24 Correct 2079 ms 52568 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 694 ms 13208 KB Output is correct
27 Correct 339 ms 52940 KB Output is correct
28 Correct 2310 ms 60608 KB Output is correct
29 Correct 2366 ms 61036 KB Output is correct
30 Correct 2514 ms 61288 KB Output is correct
31 Correct 2448 ms 61600 KB Output is correct
32 Correct 2386 ms 61700 KB Output is correct