oj.uz

Submission #543301

# Submission time Handle Problem Language Result Execution time Memory
543301 2022-03-30T06:01:26 Z Aktan Snowball (JOI21_ho_t2) C++14
0 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define ft first
#define sc second
const int mod=1e9+7,INF=1e17,N=2e5+10;

int mn[N],mx[N],ans[N];
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,q;
	cin >> n >> q;
	vector<int> a(n+1),b(q+1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	int cnt=0;
	for(int i=1;i<=q;i++){
		cin >> b[i];
		cnt+=b[i];
		mn[i]=min(mn[i-1],cnt);
		mx[i]=max(mx[i-1],cnt);
	}
	ans[1]+=abs(mn[q]);
    ans[n]+=mx[q];
	for(int i=1;i<n;i++){
		int l=1,r=q;
		while(l<r){
			int m=(l+r)/2;
			if(a[i]+mx[m]>a[i+1]+mn[m]){
				r=m;
			}
			else{
				l=m+1;
			}
		}
		if(b[l]>0){
                ans[i]+=max(0ll,a[i+1]+mn[l-1]-a[i]);
                ans[i+1]+=max(0ll,a[i+1]-(a[i+1]+mn[l-1]));
        }
		else{
                ans[i]+=max(0ll,a[i]+mx[l-1]-a[i]);
                ans[i+1]+=max(0ll,a[i+1]-a[i]-mx[l-1]);
        }
	}
	for(int i=1;i<=n;i++){
		cout << ans[i] << "\n";
	}
	
}

Compilation message

Main.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(){
      | ^~~~

Subtask #1
0 / 33.0

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

Subtask #2
0 / 67.0

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