oj.uz

Submission #1043071

# Submission time Handle Problem Language Result Execution time Memory
1043071 2024-08-03T21:24:39 Z Dan4Life Distributing Candies (IOI21_candies) C++17
38 / 100
 1982 ms 14164 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 suf[mxN], mxsuf[mxN], mnsuf[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]=-0; mnsuf[q]=0; suf[q]=0;
		for(int i = q-1; i >= 0; i--) suf[i]=suf[i+1]+v[i];
		for(int i = q-1; i >= 0; i--) mxsuf[i]=max(mxsuf[i+1],suf[i]);
		for(int i = q-1; i >= 0; i--) mnsuf[i]=min(mnsuf[i+1],suf[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;
				if(ans[i]>=c[i]) ans[i]=c[i],k=j;
			}*/
			ans[i] = 0;
			if(mxsuf[0]-mnsuf[0] < c[i]){
				ans[i]+=suf[0]; continue;
			}
			int L = 0, R = q-1;
			while(L<R){
				int mid = (L+R+1)/2;
				if(mxsuf[mid]-mnsuf[mid] >= c[i]) L=mid;
				else R=mid-1;
			}
			//cout << abs(k) << " " << L << " " << k << "\n";
			if(suf[L]>=suf[L+1]) ans[i]=c[i];
			ans[i]+=suf[L+1];
		}
	}
	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: unused variable 'k' [-Wunused-variable]
   23 |    int k = 0;
      |        ^

Subtask #1
3.0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1910 ms 12220 KB Output is correct
2 Correct 1889 ms 11424 KB Output is correct
3 Correct 1922 ms 11400 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 50 ms 8020 KB Output is correct
3 Correct 46 ms 5952 KB Output is correct
4 Correct 1982 ms 13416 KB Output is correct
5 Correct 1868 ms 13804 KB Output is correct
6 Correct 1958 ms 14164 KB Output is correct
7 Correct 1967 ms 13528 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 4444 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1910 ms 12220 KB Output is correct
7 Correct 1889 ms 11424 KB Output is correct
8 Correct 1922 ms 11400 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 50 ms 8020 KB Output is correct
11 Correct 46 ms 5952 KB Output is correct
12 Correct 1982 ms 13416 KB Output is correct
13 Correct 1868 ms 13804 KB Output is correct
14 Correct 1958 ms 14164 KB Output is correct
15 Correct 1967 ms 13528 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -