Submission #506171

#	Time	Username	Problem	Language	Result	Execution time	Memory
506171		Koosha_mv	Sparklers (JOI17_sparklers)	C++14	100 / 100	111 ms	6620 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=2e5+9,inf=1e10+9;

int n,k,t,a[N];

vector<int> g(vector<int> v,int x){
	vector<int> res;
	int pos=0;
	f(i,0,v.size()){
		if(v[i]>v[pos]){
			pos=i;
		}
	}
	if(x==0){
		f(i,0,pos+1){
			res.pb(v[i]);
		}
	}
	else{
		f_(i,v.size()-1,pos){
			res.pb(v[i]);
		}
	}
	return res;
}
bool solve(vector<int> v0,vector<int> v1){
	int p0=0,p1=0,mn0=inf,mn1=inf;
	if(v0[p0]+v1[p1]<0) return 0;
//	dbgv(v0);
//	dbgv(v1);
	f(i,1,v0.size()){
		minm(mn0,v0[i]);
		if(v0[i]>=v0[0]){
			break;
		}
	}
	f(i,1,v1.size()){
		minm(mn1,v1[i]);
		if(v1[i]>=v1[0]){
			break;
		}
	}
//	cout<<mn0<<" "<<mn1<<endl;
	while(p0+1<v0.size() || p1+1<v1.size()){
//		cout<<p0<<" "<<p1<<endl;
		if(p0+1<v0.size() && mn0+v1[p1]>=0){
			f(j,p0+1,v0.size()){
				if(v0[j]>=v0[p0]){
					p0=j;
					break;
				}
			}
			mn0=inf;
			f(j,p0+1,v0.size()){
				minm(mn0,v0[j]);
				if(v0[j]>=v0[p0]){
					break;
				}
			}
		}
		else if(p1+1<v1.size() && mn1+v0[p0]>=0){
			f(j,p1+1,v1.size()){
				if(v1[j]>=v1[p1]){
					p1=j;
					break;
				}
			}
			mn1=inf;
			f(j,p1+1,v1.size()){
				minm(mn1,v1[j]);
				if(v1[j]>=v1[p1]){
					break;
				}
			}
		}
		else{
			return 0;
		}
	}
	return 1;
}
bool check(int s){
	vector<int> v0,v1;
	v0.pb(0);
	v1.pb(0);
	f_(i,k-1,0){
		v0.pb(-(a[k]-a[i]-s*(k-i)));
	}
	f(i,k+1,n){
		v1.pb(-(a[i]-a[k]-s*(i-k)));
	}
//	dbgv(v0);
//	dbgv(v1);
	return solve(g(v0,0),g(v1,0)) && solve(g(v0,1),g(v1,1));
}

main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>k>>t; k--;
	f(i,0,n){
		cin>>a[i];
	}
	//eror(check(150));
	//exit(0);
	int l=-1,r=inf;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(2ll*t*mid)) r=mid;
		else l=mid;
	}
	cout<<r;
}

Compilation message (stderr)

sparklers.cpp: In function 'std::vector<long long int> g(std::vector<long long int>, long long int)':
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   31 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
sparklers.cpp:31:2: note: in expansion of macro 'f'
   31 |  f(i,0,v.size()){
      |  ^
sparklers.cpp: In function 'bool solve(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   53 |  f(i,1,v0.size()){
      |    ~~~~~~~~~~~~~               
sparklers.cpp:53:2: note: in expansion of macro 'f'
   53 |  f(i,1,v0.size()){
      |  ^
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   59 |  f(i,1,v1.size()){
      |    ~~~~~~~~~~~~~               
sparklers.cpp:59:2: note: in expansion of macro 'f'
   59 |  f(i,1,v1.size()){
      |  ^
sparklers.cpp:66:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  while(p0+1<v0.size() || p1+1<v1.size()){
      |        ~~~~^~~~~~~~~~
sparklers.cpp:66:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  while(p0+1<v0.size() || p1+1<v1.size()){
      |                          ~~~~^~~~~~~~~~
sparklers.cpp:68:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(p0+1<v0.size() && mn0+v1[p1]>=0){
      |      ~~~~^~~~~~~~~~
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   69 |    f(j,p0+1,v0.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:69:4: note: in expansion of macro 'f'
   69 |    f(j,p0+1,v0.size()){
      |    ^
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   76 |    f(j,p0+1,v0.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:76:4: note: in expansion of macro 'f'
   76 |    f(j,p0+1,v0.size()){
      |    ^
sparklers.cpp:83:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   else if(p1+1<v1.size() && mn1+v0[p0]>=0){
      |           ~~~~^~~~~~~~~~
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   84 |    f(j,p1+1,v1.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:84:4: note: in expansion of macro 'f'
   84 |    f(j,p1+1,v1.size()){
      |    ^
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   91 |    f(j,p1+1,v1.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:91:4: note: in expansion of macro 'f'
   91 |    f(j,p1+1,v1.size()){
      |    ^
sparklers.cpp: At global scope:
sparklers.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main(){
      | ^~~~

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