oj.uz

Submission #492666

# Submission time Handle Problem Language Result Execution time Memory
492666 2021-12-08T11:01:39 Z lukameladze Distributing Candies (IOI21_candies) C++17
11 / 100
 2636 ms 60212 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 = -1e9;
	vector <int> anss;
	anss.clear();
	emp.mn = 1e9;
	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 6 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 6 ms 7756 KB Output is correct
4 Correct 8 ms 7796 KB Output is correct
5 Correct 22 ms 7820 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2621 ms 56088 KB Output is correct
2 Correct 2615 ms 60212 KB Output is correct
3 Correct 2636 ms 60040 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.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 155 ms 47780 KB Output is correct
4 Correct 812 ms 12088 KB Output is correct
5 Correct 2037 ms 52712 KB Output is correct
6 Correct 2060 ms 52848 KB Output is correct
7 Incorrect 2065 ms 52660 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 6 ms 7756 KB Output is correct
4 Correct 8 ms 7796 KB Output is correct
5 Correct 22 ms 7820 KB Output is correct
6 Correct 2621 ms 56088 KB Output is correct
7 Correct 2615 ms 60212 KB Output is correct
8 Correct 2636 ms 60040 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Incorrect 316 ms 50284 KB Output isn't correct
11 Halted 0 ms 0 KB -