Submission #396128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
396128	2021-04-29T13:35:32 Z	Knps4422	Snowball (JOI21_ho_t2)	C++14	0 / 100	2500 ms	332 KB

Main

//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
typedef complex<int> point;
const int nmax = 400005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = 1e9;
const int sq = 5000;

int n, q;
ll pos[nmax], wind[nmax];
ll lef[nmax], rig[nmax];
ll cnt[nmax];
int main(){
	cin >> n >> q;
	for (int i = 0; i < n; ++i)
	{
		cin >> pos[i];
	}
	ll ps = 0;
	for (int i = 0; i < q; ++i)
	{
		cin >> wind[i];
		ps += wind[i];
		rig[i] = max(rig[i] , ps);
		rig[i+1] = rig[i];
		lef[i] = min(lef[i] , ps);
		lef[i+1] = lef[i];
	}
	cnt[0] -= lef[q-1];
	cnt[n-1] += rig[q-1];
	for(int i = 0; i < n; i++){
		ll l = pos[i] , r = pos[i+1];
		while(l < r){
			ll mid = (l+r)/2;
			int lt = 0, rt = n-1;
			while(lt < rt){
				int md = (lt+rt)/2;
				if(pos[i] + rig[md] - 1 >= mid){
					rt = md;
				}else{
					lt = md+1;
				}
			}
			int t1 = lt;
			lt = 0, rt = n-1;
			while(lt < rt){
				int md = (lt+rt)/2;
				if(pos[i+1] + lef[md] <= mid){
					rt = md;
				}else{
					lt = md+1;
				}
			}
			int t2 = lt;
			if(t1 < t2){
				l = mid+1;
			}else{
				r = mid;
			}
		}
		//cout << i << ' ' << l << '\n';
		cnt[i] += l - pos[i];
		cnt[i+1] += pos[i+1] - l;
	}
	for(int i = 0; i < n; i++){
		cout << cnt[i] << '\n';
	}
	cout << '\n';

}

Subtask #1

0 / 33.0

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

Subtask #2

0 / 67.0

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