Submission #113796

#	Time	Username	Problem	Language	Result	Execution time	Memory
113796		aminra	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	384 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)2e18;
ll n, k, t, X[MAXN];
bool make(vector<ll> x, vector<ll> y)
{
	if (x[0] < y[0])
		return 0;
  	int ok = 1;
  	pair<int, int> L, R;
  	L = {0, 0};
  	R = {0, 0};
  	while (ok) 
	{
	    ok = 0;
	    while (L.first + 1 < x.size() && x[L.first + 1] >= y[R.second])
		{
	    	ok = 1;
	    	if(x[++L.first] > x[L.second]) 
				L.second = L.first;
	    }
	    while (R.first + 1 < y.size() && y[R.first + 1] <= x[L.second])
		{
	    	ok = 1;
	    	if(y[++R.first] < y[R.second])
				R.second = R.first;
	    }
  	}
	return L.first + 1 == x.size() && R.first + 1 == y.size();
}
 
bool check(int s)
{
	vector <ll> x, y;
	for (int i = k; i >= 0; i--)
    	x.push_back(X[i] - 1LL * 2 * s * t * i);
  	for (int i = k; i < n; i++)
    	y.push_back(X[i] - 1LL * 2 * s * t * i);
	if (!make(x, y)) return 0;
	reverse(x.begin(), x.end());
	reverse(y.begin(), y.end());
	if (!make(x, y)) return 0;
	return 1;
}
 
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
  	cin >> n >> k >> t;
  	k--;
  	for (int i = 0; i < n; i++)
    	cin >> X[i];
  	int L = 0, R = infint;
  	while(R - L > 1)
  	{
  		int mid = (L + R) >> 1;
    	if(check(mid))
      		R = mid;
   		else
   			L = mid;
    }
  	cout << R;
}

Compilation message (stderr)

sparklers.cpp: In function 'bool make(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:21:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (L.first + 1 < x.size() && x[L.first + 1] >= y[R.second])
             ~~~~~~~~~~~~^~~~~~~~~~
sparklers.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (R.first + 1 < y.size() && y[R.first + 1] <= x[L.second])
             ~~~~~~~~~~~~^~~~~~~~~~
sparklers.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return L.first + 1 == x.size() && R.first + 1 == y.size();
         ~~~~~~~~~~~~^~~~~~~~~~~
sparklers.cpp:34:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return L.first + 1 == x.size() && R.first + 1 == y.size();
                                    ~~~~~~~~~~~~^~~~~~~~~~~

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