oj.uz

Submission #1043077

# Submission time Handle Problem Language Result Execution time Memory
1043077 2024-08-03T22:10:46 Z Dan4Life Distributing Candies (IOI21_candies) C++17
38 / 100
 1986 ms 7504 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
const int mxN = (int)2e5+10;
const ll LINF = (ll)1e18;
ll mxsuf[mxN], mnsuf[mxN], pref[mxN];

vi distribute_candies(vi c, vi l, vi r, vi v){
    int n = sz(c), q = sz(l); vector<int> ans(n,0);
    if(*max_element(all(l))==0 and *min_element(all(r))==n-1){
		mxsuf[q+1]=-LINF; mnsuf[q+1]=LINF; pref[0]=0;
		for(int i = 0; i < q; i++) pref[i+1]=pref[i]+v[i];
		for(int i = q; i >= 0; i--) mxsuf[i]=max(mxsuf[i+1],pref[i]);
		for(int i = q; i >= 0; i--) mnsuf[i]=min(mnsuf[i+1],pref[i]);
		for(int i = 0; i < n; i++){
			int k = 0;
			for(int j = 0; j < q; j++){
				ans[i]+=v[j];
				if(ans[i]<=0) ans[i]=0,k=-(j+1);
				if(ans[i]>=c[i]) ans[i]=c[i],k=(j+1);
			}
			ans[i] = 0;
			if(mxsuf[0]-mnsuf[0] < c[i]){
				ans[i]+=pref[q]; continue;
			}
			int L = 0, R = q;
			while(L<R){
				int mid = (L+R+1)/2;
				if(mxsuf[mid]-mnsuf[mid] >= c[i]) L=mid;
				else R=mid-1;
			}
			L++;
			if(v[L-1]>0) ans[i]=c[i];
			ans[i]+=pref[q]-pref[L];
		}
	}
	else{
		for(int i = 0; i < q; i++){
			for(int j = l[i]; j <= r[i]; j++){
				ans[j]+=v[i]; ans[j]=min(ans[j],c[j]);
				ans[j]=max(ans[j],0);
			}
		}
	}
    return ans;
}

Compilation message

candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:23:8: warning: variable 'k' set but not used [-Wunused-but-set-variable]
   23 |    int k = 0;
      |        ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1964 ms 7492 KB Output is correct
2 Correct 1944 ms 7248 KB Output is correct
3 Correct 1908 ms 7416 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 54 ms 5112 KB Output is correct
3 Correct 44 ms 3908 KB Output is correct
4 Correct 1968 ms 7248 KB Output is correct
5 Correct 1986 ms 7496 KB Output is correct
6 Correct 1956 ms 7504 KB Output is correct
7 Correct 1916 ms 7496 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1964 ms 7492 KB Output is correct
7 Correct 1944 ms 7248 KB Output is correct
8 Correct 1908 ms 7416 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 54 ms 5112 KB Output is correct
11 Correct 44 ms 3908 KB Output is correct
12 Correct 1968 ms 7248 KB Output is correct
13 Correct 1986 ms 7496 KB Output is correct
14 Correct 1956 ms 7504 KB Output is correct
15 Correct 1916 ms 7496 KB Output is correct
16 Incorrect 0 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -