Submission #578494

#	Time	Username	Problem	Language	Result	Execution time	Memory
578494		alireza_kaviani	Sparklers (JOI17_sparklers)	C++17	100 / 100	57 ms	4840 KiB

sparklers

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 2e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , k , t , A[MAXN];
vector<ll> L , R;

int check(ll s){
	int n = SZ(L) , m = SZ(R);
	vector<ll> x = {0} , y = {0};
	for(int i = 0 ; i < n ; i++){
		x.push_back(L[i] - 2 * s * t * (i + 1));
	}
	for(int i = 0 ; i < m ; i++){
		y.push_back(R[i] - 2 * s * t * (i + 1));
	}
	ll xpos = min_element(all(x)) - x.begin();
	ll ypos = min_element(all(y)) - y.begin();
	ll xptr = 0 , yptr = 0 , xmn = 0 , ymn = 0;
	while(xptr <= xpos || yptr <= ypos){
		if(xptr <= xpos && x[xptr] + ymn <= 0){
			xmn = min(xmn , x[xptr++]);
			continue;
		}
		if(yptr <= ypos && xmn + y[yptr] <= 0){
			ymn = min(ymn , y[yptr++]);
			continue;
		}
		break;
	}
	if(xptr <= xpos || yptr <= ypos)	return 0;
	xptr = n , yptr = m , xmn = x.back() , ymn = y.back();
	while(xptr >= xpos || yptr >= ypos){
		if(xptr >= xpos && x[xptr] + ymn <= 0){
			xmn = min(xmn , x[xptr--]);
			continue;
		}
		if(yptr >= ypos && xmn + y[yptr] <= 0){
			ymn = min(ymn , y[yptr--]);
			continue;
		}
		break;
	}
	return (xptr < xpos && yptr < ypos);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> k >> t;
	for(int i = 1 ; i <= n ; i++){
		cin >> A[i];
	}
	for(int i = k - 1 ; i >= 1 ; i--){
		L.push_back(A[k] - A[i]);
	}
	for(int i = k + 1 ; i <= n ; i++){
		R.push_back(A[i] - A[k]);
	}
	int l = -1 , r = MOD;
	while(r - l > 1){
		int mid = l + r >> 1;
		if(check(mid))	r = mid;
		else	l = mid;
	}
	cout << r << endl;

    return 0;
}
/*

*/

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50