oj.uz

Submission #917452

# Submission time Handle Problem Language Result Execution time Memory
917452 2024-01-28T08:19:42 Z PM1 MP3 Player (CEOI10_mp3player) C++17
60 / 100
 271 ms 15212 KB 
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const ll mxn=2e5+5,sz=(1<<22);
ll n,vmx,v2,t[mxn],a[mxn],last;
vector<pair<ll,ll>>v;
struct segment{
	ll mx[sz],mn[sz],lazy[sz];
	void shift(ll id){
		for(ll i=0;i<2;i++){
			mx[id*2+i]+=lazy[id];
			mn[id*2+i]+=lazy[id];
			lazy[id*2+i]+=lazy[id];
		}
		lazy[id]=0;
	}
	void add(ll id,ll L,ll R,ll l,ll r,ll x){
		if(L==l && R==r){
			lazy[id]+=x;
			mx[id]+=x;
			mn[id]+=x;
			return ;
		}
		if(lazy[id])
			shift(id);
		ll mid=(L+R)/2;
		if(l<mid)
			add(id*2,L,mid,l,min(r,mid),x);
		if(r>mid)
			add(id*2+1,mid,R,max(l,mid),r,x);
		mx[id]=max(mx[id*2],mx[id*2+1]);
		mn[id]=min(mn[id*2],mn[id*2+1]);
	}
}seg;
int main(){
	cin>>n>>vmx>>v2;
	for(ll i=1;i<=n;i++){
		char x;
		cin>>x>>t[i];
		if(x=='+')a[i]=1;
		else a[i]=-1;
		if(i!=1)seg.add(1,1,n+2,1,i+1,-a[i]);
	}
	seg.add(1,1,n+2,1,n+2,v2);
	for(ll i=n;i>1;i--){
		t[i]-=t[i-1];
		v.push_back({t[i],i});
	}
	v.push_back({0,0});
	sort(v.begin(),v.end());
	ll p=v.back().fr;
	while(v.size()){//cout<<seg.mx[1]<<" "<<seg.mn[1]<<endl;
		if(seg.mx[1]<=vmx && seg.mn[1]>=0)break;
		while(v.back().fr==p){
			seg.add(1,1,n+2,1,v.back().sc+1,a[v.back().sc]);
			v.pop_back();
		}
		last=p;
		p=v.back().fr;
	}
	if(v.size()==n){
		cout<<"infinity";
		return 0;
	}
	cout<<last-1<<" ";
	ll l=0,r=vmx+1,y=last-1;
	for(ll j=vmx;j>=0;j--){
		ll x=j;
		for(ll i=2;i<=n;i++){
			if(y>=t[i]){
				x+=a[i];
				x=max((ll)0,x);
				x=min(x,vmx);
			}
		}
		if(x==v2){
			cout<<j;
			return 0;
		}
	}

}

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:63:13: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   63 |  if(v.size()==n){
      |     ~~~~~~~~^~~
mp3player.cpp:68:5: warning: unused variable 'l' [-Wunused-variable]
   68 |  ll l=0,r=vmx+1,y=last-1;
      |     ^
mp3player.cpp:68:9: warning: unused variable 'r' [-Wunused-variable]
   68 |  ll l=0,r=vmx+1,y=last-1;
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7156 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 4 ms 6748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6748 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6744 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 11992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 11992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 11984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 13036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 15008 KB Output is correct
2 Correct 83 ms 15044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 15180 KB Output is correct
2 Correct 77 ms 15212 KB Output is correct