oj.uz

Submission #506168

# Submission time Handle Problem Language Result Execution time Memory
506168 2022-01-11T19:56:32 Z Koosha_mv Sparklers (JOI17_sparklers) C++14
0 / 100
 0 ms 324 KB 
#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;
	//dbgv(v0);
	//dbgv(v1);
	f(i,0,v0.size()){
		minm(mn0,v0[i]);
		if(v0[i]>=v0[0]){
			break;
		}
	}
	f(i,0,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,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,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(100));
	//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

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++)
......
   52 |  f(i,0,v0.size()){
      |    ~~~~~~~~~~~~~               
sparklers.cpp:52:2: note: in expansion of macro 'f'
   52 |  f(i,0,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++)
......
   58 |  f(i,0,v1.size()){
      |    ~~~~~~~~~~~~~               
sparklers.cpp:58:2: note: in expansion of macro 'f'
   58 |  f(i,0,v1.size()){
      |  ^
sparklers.cpp:65: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]
   65 |  while(p0+1<v0.size() || p1+1<v1.size()){
      |        ~~~~^~~~~~~~~~
sparklers.cpp:65: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]
   65 |  while(p0+1<v0.size() || p1+1<v1.size()){
      |                          ~~~~^~~~~~~~~~
sparklers.cpp:67: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]
   67 |   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++)
......
   68 |    f(j,p0+1,v0.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:68:4: note: in expansion of macro 'f'
   68 |    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++)
......
   75 |    f(j,p0,v0.size()){
      |      ~~~~~~~~~~~~~~            
sparklers.cpp:75:4: note: in expansion of macro 'f'
   75 |    f(j,p0,v0.size()){
      |    ^
sparklers.cpp:82: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]
   82 |   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++)
......
   83 |    f(j,p1+1,v1.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:83:4: note: in expansion of macro 'f'
   83 |    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++)
......
   90 |    f(j,p1,v1.size()){
      |      ~~~~~~~~~~~~~~            
sparklers.cpp:90:4: note: in expansion of macro 'f'
   90 |    f(j,p1,v1.size()){
      |    ^
sparklers.cpp: At global scope:
sparklers.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  118 | main(){
      | ^~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 324 KB Output isn't correct
4 Halted 0 ms 0 KB -