Submission #57760

#	Time	Username	Problem	Language	Result	Execution time	Memory
57760		spencercompton	Sparklers (JOI17_sparklers)	C++17	100 / 100	212 ms	31820 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll t;
bool v[1001][1001];
ll pos[1001];
// ll dp[2][1000][1000];
// ll pos[1000];
vector<ll> all;
int main(){
	ll tt;
	cin >> n >> k >> tt;
	for(int i = 0; i<n; i++){
		cin >> pos[i];
	}
	k--;
	ll low = 0LL;
	ll high = 1000000000LL;
	while(low<high){
		ll mid = (low+high)/2LL;
		t = mid*tt;
		vector<ll> ar[2];
		for(int i = 0; i<2; i++){
			ar[i].push_back(0);
		}
		for(int i = k+1; i<n; i++){
			ar[0].push_back(ar[0][ar[0].size()-1] + 2LL * t - (pos[i]-pos[i-1]));
		}
		for(int i = k-1; i>=0; i--){
			ar[1].push_back(ar[1][ar[1].size()-1] + 2LL * t - (pos[i+1] - pos[i]));
		}
		// if(mid==9){
		// 	cout << "Q " << endl;
		// 	for(int i = 0; i<2; i++){
		// 		for(int j = 0; j<ar[i].size(); j++){
		// 			cout << ar[i][j] << " " ;
		// 		}
		// 		cout << endl;
		// 	}
		// }
		vector<pair<int, ll> > f[2];
		vector<pair<int, ll> > b[2];
		vector<ll> pre[2];
		for(int i = 0; i<2; i++){
			f[i].push_back(make_pair(0,0));
			int sz = 1;
			for(int j = 1; j<ar[i].size(); j++){
				if(ar[i][j] > ar[i][f[i][sz-1].first]){
					sz++;
					f[i].push_back(make_pair(j,ar[i][j]));
				}
			}
			for(int j = 0; j+1<sz; j++){
				for(int a = f[i][j].first; a<f[i][j+1].first; a++){
					f[i][j].second = min(f[i][j].second,ar[i][a]);
				}
			}
			sz = 1;
			b[i].push_back(make_pair(ar[i].size()-1,ar[i][ar[i].size()-1]));
			for(int j = ar[i].size()-2; j>=0; j--){
				if(ar[i][j] > ar[i][b[i][sz-1].first]){
					sz++;
					b[i].push_back(make_pair(j,ar[i][j]));
				}
			}
			for(int j = sz-1; j>0; j--){
				for(int a = b[i][j].first; a<b[i][j-1].first; a++){
					b[i][j].second = min(b[i][j].second,ar[i][a]);
				}
			}
			pre[i].resize(sz);
			pre[i][0] = b[i][0].second;
			for(int j = 1; j<sz; j++){
				pre[i][j] = min(b[i][j].second,pre[i][j-1]);
			}
		}
		bool ok = true;
		int p1 = 0;
		int p2 = 0;
		while(p1+1<f[0].size() || p2+1<f[1].size()){
			if(p1+1<f[0].size() && ar[1][f[1][p2].first] + f[0][p1].second >=0LL){
				p1++;
			}
			else if(p2+1<f[1].size() && ar[0][f[0][p1].first] + f[1][p2].second >= 0LL){
				p2++;
			}
			else{
				ok = false;
				break;
			}
		}
		if(!ok){
			low = mid+1LL;
			continue;
		}
		p1 = b[0].size()-1;
		p2 = b[1].size()-1;
		// if(mid==9){
		// 	for(int i = 0; i<2; i++){
		// 		for(int j = 0; j<b[i].size(); j++){
		// 			cout  << b[i][j].first <<"," << b[i][j].second << " ";
		// 		}
		// 		cout << endl;
		// 	}
		// 	for(int i = 0; i<2; i++){
		// 		for(int j = 0; j<pre[i].size(); j++){
		// 			cout << pre[i][j] << " ";
		// 		}
		// 		cout << endl;
		// 	}
		// }
		while(p1>0 || p2>0){
			if(p1>0 && ar[1][b[1][p2].first] + b[0][p1].second >= 0LL && ar[0][b[0][p1-1].first] + pre[1][p2] >=0LL){
				p1--;
			}
			else if(p2>0 && ar[0][b[0][p1].first] + b[1][p2].second >= 0LL && ar[1][b[1][p2-1].first] + pre[0][p1] >=0LL){
				p2--;
			}
			else {
				ok = false;
				break;
			}
		}
		if(!ok){
			low = mid+1LL;
		}
		else{
			high = mid;
		}
	}
	cout << low << endl;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 1; j<ar[i].size(); j++){
                   ~^~~~~~~~~~~~~
sparklers.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<f[0].size() || p2+1<f[1].size()){
         ~~~~^~~~~~~~~~~~
sparklers.cpp:81:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<f[0].size() || p2+1<f[1].size()){
                             ~~~~^~~~~~~~~~~~
sparklers.cpp:82:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(p1+1<f[0].size() && ar[1][f[1][p2].first] + f[0][p1].second >=0LL){
       ~~~~^~~~~~~~~~~~
sparklers.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(p2+1<f[1].size() && ar[0][f[0][p1].first] + f[1][p2].second >= 0LL){
            ~~~~^~~~~~~~~~~~

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