oj.uz

Submission #253545

# Submission time Handle Problem Language Result Execution time Memory
253545 2020-07-28T07:56:14 Z Markoes Potatoes and fertilizers (LMIO19_bulves) C++14
24 / 100
 219 ms 24792 KB 
#include<bits/stdc++.h>

using namespace std;
int n,a,b[500005],c[500005],id,val;
vector<pair<int,int> > va,slv;
set<int> vb;
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i]>>a;
		if(a<b[i]){
			b[i] -= a;
			a = 0;
		}
		else{
			a -= b[i];
			b[i] = 0;
		}
		if(a>0){
			va.push_back(make_pair(i,a));
		}
		if(b[i]>0){
			vb.insert(i);
		}
	}
	long long aa=0;
	memset(c,0,sizeof c);
	for(auto x : va){
		id = x.first;
		val = x.second;
		aa += val;
		
		//cout<<id<<"-id  val-"<<val<<endl;;
		while(val>0){
			auto kanan = vb.lower_bound(id);
//			cout<<*kanan<<endl;
			if(kanan == vb.begin()){
//				cout<<"depan"<<endl;
				if(b[*kanan] <= val){
					val -= b[*kanan];
					vb.erase(kanan);
					//slv.push_back(make_pair(*kanan,b[*kanan]));
					c[*kanan] += b[*kanan];
				}
				else{
					b[*kanan] -= val;
					//slv.push_back(make_pair(*kanan,val));
					c[*kanan] += val;
					val = 0;
				}
				continue;
			}
			if(kanan == vb.end()){
//				cout<<"belakang"<<endl;
				kanan--;
				if(b[*kanan] <= val){
					val -= b[*kanan];
					vb.erase(kanan);
					//slv.push_back(make_pair(*kanan,b[*kanan]));
					c[*kanan] += b[*kanan];
				}
				else{
					b[*kanan] -= val;
					//slv.push_back(make_pair(*kanan,val));
					c[*kanan] += val;
					val = 0;
				}
				continue;
			}
			auto kiri = kanan;
			kiri--;
//			cout<<*kiri<<' '<<*kanan<<endl;
			if(id - *kiri > *kanan - id){
				if(b[*kanan] <= val){
					val -= b[*kanan];
					vb.erase(kanan);
					c[*kanan] += b[*kanan];
					//slv.push_back(make_pair(*kanan,b[*kanan]));
				}
				else{
					b[*kanan] -= val;
					//slv.push_back(make_pair(*kanan,val));
					c[*kanan] += val;
					val = 0;
				}
			}
			else{
				if(b[*kiri] <= val){
					val -= b[*kiri];
					vb.erase(kiri);
					//slv.push_back(make_pair(*kiri,b[*kiri]));
					c[*kiri] += b[*kiri];
				}
				else{
					b[*kiri] -= val;
					//slv.push_back(make_pair(*kiri,val));
					c[*kiri] += val;
					val = 0;
				}
			}
		}
	}
//	long long cc=0;;
//	for(int i=1;i<=n;i++){
//		cc += c[i];
//		cout<<i<<' '<<c[i]<<endl;
//	}
//	cout<<endl;
//	assert(cc==aa);
	int v;
	long long ans=0;
	v = 1;
	for(auto x: va){
//		cout<<x.first<<" id"<<endl;
		while(c[v]<=x.second && v<n){
//			cout<<c[v]<<' '<<c[v] * 1ll * abs(v-x.first)<<endl;
			ans += c[v] * 1ll * abs(v-x.first);
			x.second -= c[v];
			v++;
		}
//		cout<<x.second * 1ll * abs(v-x.first)<<endl;
		ans += x.second * 1ll * abs(v-x.first);
		c[v] -= x.second;
	}
	cout<<ans<<endl;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2304 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 16 ms 4220 KB Output is correct
5 Correct 32 ms 6128 KB Output is correct
6 Correct 81 ms 9340 KB Output is correct
7 Correct 219 ms 24792 KB Output is correct
8 Correct 162 ms 23032 KB Output is correct
9 Correct 183 ms 22244 KB Output is correct
10 Correct 142 ms 20012 KB Output is correct
11 Correct 150 ms 20052 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2304 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 16 ms 4220 KB Output is correct
5 Correct 32 ms 6128 KB Output is correct
6 Correct 81 ms 9340 KB Output is correct
7 Correct 219 ms 24792 KB Output is correct
8 Correct 162 ms 23032 KB Output is correct
9 Correct 183 ms 22244 KB Output is correct
10 Correct 142 ms 20012 KB Output is correct
11 Correct 150 ms 20052 KB Output is correct
12 Incorrect 44 ms 7280 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2304 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2304 KB Output is correct
5 Incorrect 1 ms 2304 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2304 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2304 KB Output is correct
5 Incorrect 1 ms 2304 KB Output isn't correct
6 Halted 0 ms 0 KB -