oj.uz

Submission #1043072

# Submission time Handle Problem Language Result Execution time Memory
1043072 2024-08-03T21:26:54 Z Dan4Life Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 10832 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 and 0){
		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 < n; i++){
			for(int j = 0; j < q; j++){
				ans[i]+=v[j]; ans[i]=min(ans[i],c[i]);
				ans[i]=max(ans[i],0);
			}
		}/*
		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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5021 ms 7256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1239 ms 7912 KB Output is correct
4 Correct 353 ms 4032 KB Output is correct
5 Execution timed out 5016 ms 10832 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -