oj.uz

Submission #609771

# Submission time Handle Problem Language Result Execution time Memory
609771 2022-07-27T21:41:50 Z StrawHatWess Distributing Candies (IOI21_candies) C++17
11 / 100
 106 ms 10696 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std; 

#define FOR(i,a,b) for(int i=a; i<b; i++)
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)


typedef pair<int,int>pi; 
#define fi first
#define se second
typedef vector<pi>vpi;
#define eb emplace_back

bool ckmin(int &x, int y){
	bool f=(x>y); 
	x=min(x,y); 
	return f; 
}

bool ckmax(int &x, int y){
	bool f=(x<y); 
	x=max(x,y); 
	return f; 
}

//-------

int N,Q;

vi distribute_candies(vi C, vi L, vi R, vi V) {
    N=sz(C); Q=sz(L); 

    if(max(N,Q)<=2000){
    	vi ans(N,0); 
	    FOR(i,0,Q){
	    	int l=L[i], r=R[i]; 
	    	FOR(j,l,r+1){
	    		ans[j]+=V[i]; 
	    		ckmax(ans[j],0); 
	    		ckmin(ans[j],C[j]); 
	    	}
	    }
	    return ans;
    }

    vector<ll>q(N+1,0);
    FOR(i,0,Q){
    	int l=L[i], r=R[i]; 
    	q[l]+=V[i];
    	q[r+1]-=V[i];  
    }

    ll cur=0; 
    vi ans(N); 
    FOR(i,0,N){
    	cur+=q[i];
    	ans[i]=min((ll)C[i],cur); 
    }
    return ans;
    
}

/*

3
10 15 13
2
0 2 20
0 1 -11

0 4 13


*/

Subtask #1
3.0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10696 KB Output is correct
2 Correct 95 ms 9420 KB Output is correct
3 Correct 106 ms 9380 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 4 ms 308 KB Output is correct
6 Correct 106 ms 10696 KB Output is correct
7 Correct 95 ms 9420 KB Output is correct
8 Correct 106 ms 9380 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 50 ms 6104 KB Output isn't correct
11 Halted 0 ms 0 KB -