oj.uz

Submission #62027

# Submission time Handle Problem Language Result Execution time Memory
62027 2018-07-27T09:19:10 Z mohammedehab2002 Fortune Telling 2 (JOI14_fortune_telling2) C++11
4 / 100
 3000 ms 844 KB 
#include <iostream>
#include <algorithm>
using namespace std;
#define BU 1
pair<pair<int,int>,bool> p[200005];
int lim[200005],lazy[800005];
bool cmp(pair<pair<int,int>,bool> a,pair<pair<int,int>,bool> b)
{
	return (a.first.second<b.first.second);
}
int merge(int x,int y)
{
	if (!y)
	return x;
	if (!x)
	return y;
	if (y==-1)
	return 3-x;
	return y;
}
void update(int node,int st,int en,int l,int r,int f)
{
	if (st!=en)
	{
		lazy[2*node]=merge(lazy[2*node],lazy[node]);
		lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]);
		lazy[node]=0;
	}
	if (en<l || st>r || r<l)
	return;
	if (l<=st && en<=r)
	{
		lazy[node]=merge(lazy[node],f);
		return;
	}
	int mid=(st+en)/2;
	update(2*node,st,mid,l,r,f);
	update(2*node+1,mid+1,en,l,r,f);
}
long long query(int node,int st,int en,int idx)
{
	if (st!=en)
	{
		lazy[2*node]=merge(lazy[2*node],lazy[node]);
		lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]);
		lazy[node]=0;
	}
	if (st==en)
	return lazy[node];
	else
	{
		int mid=(st+en)/2;
		if (st<=idx && idx<=mid)
		return query(2*node,st,mid,idx);
		return query(2*node+1,mid+1,en,idx);
	}
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&p[i].first.first,&p[i].first.second);
		p[i].second=0;
		if (p[i].first.first>p[i].first.second)
		{
			swap(p[i].first.first,p[i].first.second);
			p[i].second=1;
		}
	}
	sort(p,p+n);
	for (int i=0;i<n;i+=BU)
	lim[i]=p[min(i+BU,n)-1].first.first;
	for (int i=0;i<n;i+=BU)
	sort(p+i,p+i+min(BU,n-i),cmp);
	for (int i=0;i<n;i++)
	update(1,0,n-1,i,i,(int)p[i].second+1);
	while (k--)
	{
		int x;
		scanf("%d",&x);
		for (int i=0;i<n;i+=BU)
		{
			if (lim[i]>x)
			{
				for (int j=i;j<min(i+BU,n);j++)
				{
					int tmp=query(1,0,n-1,j);
					if ((tmp==1 && p[j].first.first<=x) || (tmp==2 && p[j].first.second<=x))
					update(1,0,n-1,j,j,-1);
				}
				break;
			}
			int st=i-1,en=min(i+BU,n)-1;
			while (st!=en)
			{
				int mid=(st+en+1)/2;
				if (p[mid].first.second<=x)
				st=mid;
				else
				en=mid-1;
			}
			update(1,0,n-1,i,st,-1);
			update(1,0,n-1,st+1,min(i+BU,n)-1,2);
		}
	}
	long long ans=0;
	for (int i=0;i<n;i++)
	{
		if (query(1,0,n-1,i)==1)
		ans+=p[i].first.first;
		else
		ans+=p[i].first.second;
	}
	printf("%lld",ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i].first.first,&p[i].first.second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 68 ms 616 KB Output is correct
3 Correct 139 ms 616 KB Output is correct
4 Correct 125 ms 616 KB Output is correct
5 Correct 137 ms 616 KB Output is correct
6 Correct 154 ms 640 KB Output is correct
7 Correct 129 ms 724 KB Output is correct
8 Correct 225 ms 724 KB Output is correct
9 Correct 172 ms 724 KB Output is correct
10 Correct 95 ms 724 KB Output is correct
11 Correct 126 ms 724 KB Output is correct
12 Correct 125 ms 724 KB Output is correct
13 Correct 97 ms 724 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 68 ms 616 KB Output is correct
3 Correct 139 ms 616 KB Output is correct
4 Correct 125 ms 616 KB Output is correct
5 Correct 137 ms 616 KB Output is correct
6 Correct 154 ms 640 KB Output is correct
7 Correct 129 ms 724 KB Output is correct
8 Correct 225 ms 724 KB Output is correct
9 Correct 172 ms 724 KB Output is correct
10 Correct 95 ms 724 KB Output is correct
11 Correct 126 ms 724 KB Output is correct
12 Correct 125 ms 724 KB Output is correct
13 Correct 97 ms 724 KB Output is correct
14 Execution timed out 3089 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 68 ms 616 KB Output is correct
3 Correct 139 ms 616 KB Output is correct
4 Correct 125 ms 616 KB Output is correct
5 Correct 137 ms 616 KB Output is correct
6 Correct 154 ms 640 KB Output is correct
7 Correct 129 ms 724 KB Output is correct
8 Correct 225 ms 724 KB Output is correct
9 Correct 172 ms 724 KB Output is correct
10 Correct 95 ms 724 KB Output is correct
11 Correct 126 ms 724 KB Output is correct
12 Correct 125 ms 724 KB Output is correct
13 Correct 97 ms 724 KB Output is correct
14 Execution timed out 3089 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -