Submission #1125384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125384		PieArmy	Circus (Balkan15_CIRCUS)	C++20	11 / 100	22 ms	3912 KiB

circus

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "circus.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n;
int arr[100001],need[100001],mn[400005],mx[400005];

void build(int node=1,int left=0,int right=-1){
	if(right==-1)right=n-1;
	if(left==right){
		mn[node]=arr[left]+need[left];
		mx[node]=arr[left]-need[left];
		return;
	}
	build(node*2,left,mid);
	build(node*2+1,mid+1,right);
	mx[node]=max(mx[node*2],mx[node*2+1]);
	mn[node]=min(mn[node*2],mn[node*2+1]);
}

int mxwalk(int k,int node=1,int left=0,int right=-1){
	if(right==-1)right=n-1;
	if(left==right)return arr[left];
	if(mx[node*2]>=k)return mxwalk(k,node*2,left,mid);
	return mxwalk(k,node*2+1,mid+1,right);
}

int mnwalk(int k,int node=1,int left=0,int right=-1){
	if(right==-1)right=n-1;
	if(mn[node]>k)return -sonsuz;
	if(left==right)return arr[left];
	if(mn[node*2+1]<=k)return mnwalk(k,node*2+1,mid+1,right);
	return mnwalk(k,node*2,left,mid);
}

void init(int N,int M,int P[]){
	n=N+1;
	for(int i=0;i<N;i++){
		arr[i]=P[i];
	}
	sort(arr,arr+N);
	arr[n-1]=M;
	int opt[n];
	for(int &x:opt){
		x=n-1;
	}
	for(int i=n-2;i>=0;i--){
		opt[i]=min(opt[i],opt[i+1]);
		need[i]=arr[opt[i]]-arr[i];
		int l=-1,r=i-1;
		while(l<r){
			int mi=(l+r+1)/2;
			if(arr[i]-arr[mi]>=need[i]){
				l=mi;
			}
			else r=mi-1;
		}
		if(l!=-1){
			opt[l]=i;
		}
	}
	build();
}

int minLength(int D){
	return min(D-mnwalk(D),mxwalk(D)-D);
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9