답안 #1043071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043071 2024-08-03T21:24:39 Z Dan4Life 사탕 분배 (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;
      |        ^
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -