oj.uz

Submission #346858

# Submission time Handle Problem Language Result Execution time Memory
346858 2021-01-11T09:31:40 Z arnold518 MP3 Player (CEOI10_mp3player) C++14
100 / 100
 95 ms 4716 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, Vmax, V2;
pii A[MAXN+10];
int B[MAXN+10];

struct SEG
{
	int maxv[MAXN*4+10], minv[MAXN*4+10], lazy[MAXN*4+10];

	void busy(int node, int tl, int tr)
	{
		maxv[node]+=lazy[node];
		minv[node]+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	int querymin(int node, int tl, int tr)
	{
		busy(node, tl, tr);
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(minv[node*2+1]+lazy[node*2+1]<=0) return querymin(node*2+1, mid+1, tr);
		else return querymin(node*2, tl, mid);
	}
	int querymax(int node, int tl, int tr)
	{
		busy(node, tl, tr);
		if(tl==tr) return tl;
		int mid=tl+tr>>1;
		if(maxv[node*2+1]+lazy[node*2+1]>=Vmax) return querymax(node*2+1, mid+1, tr);
		else return querymax(node*2, tl, mid);
	}
	void update(int node, int tl, int tr, int l, int r, int k)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			lazy[node]+=k;
			busy(node, tl, tr);
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
		minv[node]=min(minv[node*2], minv[node*2+1]);
		maxv[node]=max(maxv[node*2], maxv[node*2+1]);
	}
	int querymin2(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r) return minv[node];
		if(r<tl || tr<l) return 987654321;
		int mid=tl+tr>>1;
		return min(querymin2(node*2, tl, mid, l, r), querymin2(node*2+1, mid+1, tr, l, r));
	}
	int querymax2(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r) return maxv[node];
		if(r<tl || tr<l) return -987654321;
		int mid=tl+tr>>1;
		return max(querymax2(node*2, tl, mid, l, r), querymax2(node*2+1, mid+1, tr, l, r));
	}
}seg;

int main()
{
	scanf("%d%d%d", &N, &Vmax, &V2); N--;
	int t;
	scanf(" %*c%d", &t);
	for(int i=1; i<=N; i++)
	{
		int p; char q;
		scanf(" %c%d", &q, &p);
		if(q=='+') A[i]={p-t, i};
		else A[i]={p-t, -i};
		t=p;
	}
	sort(A+1, A+N+1);

	int ans1=A[1].first-1, ans2=V2;
	A[N+1].first=2147483647;

	seg.update(1, 0, N+1, 0, N+1, V2);

	for(int i=1; i<=N; i++)
	{
		if(A[i].second>0) B[A[i].second]=1, seg.update(1, 0, N+1, 0, A[i].second, -1);
		else B[-A[i].second]=-1, seg.update(1, 0, N+1, 0, -A[i].second, 1);
		if(A[i].first==A[i+1].first) continue;

		if(Vmax==0) continue;

		int p=seg.querymin(1, 0, N+1);
		int q=seg.querymax(1, 0, N+1);

		if(p==0 && q==0)
		{
			ans1=A[i+1].first-1;
			ans2=seg.querymax2(1, 0, N+1, 0, 0);
		}
		else if(p<q)
		{
			if(seg.querymax2(1, 0, N+1, p, N+1)<=Vmax)
			{
				ans1=A[i+1].first-1;
				if(q==0) ans2=seg.querymax2(1, 0, N+1, 0, 0);
				else ans2=Vmax;
			}
		}
		else
		{
			if(seg.querymin2(1, 0, N+1, q, N+1)>=0)
			{
				ans1=A[i+1].first-1;
				if(q==0) ans2=seg.querymax2(1, 0, N+1, 0, 0);
				else ans2=Vmax;	
			}
		}
	}
	if(ans1==2147483646) printf("infinity\n");
	else printf("%d %d\n", ans1, ans2);
}

Compilation message

mp3player.cpp: In member function 'int SEG::querymin(int, int, int)':
mp3player.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=tl+tr>>1;
      |           ~~^~~
mp3player.cpp: In member function 'int SEG::querymax(int, int, int)':
mp3player.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid=tl+tr>>1;
      |           ~~^~~
mp3player.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
mp3player.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid=tl+tr>>1;
      |           ~~^~~
mp3player.cpp: In member function 'int SEG::querymin2(int, int, int, int, int)':
mp3player.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int mid=tl+tr>>1;
      |           ~~^~~
mp3player.cpp: In member function 'int SEG::querymax2(int, int, int, int, int)':
mp3player.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid=tl+tr>>1;
      |           ~~^~~
mp3player.cpp: In function 'int main()':
mp3player.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  scanf("%d%d%d", &N, &Vmax, &V2); N--;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf(" %*c%d", &t);
      |  ~~~~~^~~~~~~~~~~~~~
mp3player.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf(" %c%d", &q, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1388 KB Output is correct
2 Correct 19 ms 1388 KB Output is correct
3 Correct 16 ms 1516 KB Output is correct
4 Correct 14 ms 1388 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1388 KB Output is correct
2 Correct 24 ms 1388 KB Output is correct
3 Correct 21 ms 1536 KB Output is correct
4 Correct 20 ms 1516 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1516 KB Output is correct
2 Correct 25 ms 1516 KB Output is correct
3 Correct 38 ms 2540 KB Output is correct
4 Correct 18 ms 1772 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2412 KB Output is correct
2 Correct 38 ms 2924 KB Output is correct
3 Correct 34 ms 2924 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4588 KB Output is correct
2 Correct 73 ms 4588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4716 KB Output is correct
2 Correct 73 ms 4716 KB Output is correct