oj.uz

Submission #157748

# Submission time Handle Problem Language Result Execution time Memory
157748 2019-10-12T19:30:06 Z TadijaSebez Sushi (JOI16_sushi) C++11
0 / 100
 12000 ms 21724 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=400050;
const int S=200;
const int M=N/S+1;
const int Q=25050;
multiset<pair<int,int>> st[M];
int a[N],n,q,ok[M];
bool mark[N];
int Push(int B, int x)
{
	st[B].insert({x,0});
	int p;tie(x,p)=*st[B].rbegin();
	st[B].erase(--st[B].end());
	if(p) mark[-p]=1,ok[B]=0;
	return x;
}
void BuildBlock(int B, int l, int r){ for(int i=l;i<=r;i++) st[B].insert({a[i],-i}),mark[i]=0;ok[B]=1;}
void BreakBlock(int B)
{
	if(ok[B]) st[B].clear();
	else
	{
		int l=B*S,r=min((B+1)*S,n)-1;
		for(int i=r;i>=l;i--)
		{
			if(mark[i])
			{
				int x,y;tie(x,y)=*st[B].rbegin();
				st[B].erase(--st[B].end());
				a[i]=x;
				if(y) mark[-y]=1;
			}
			else
			{
				st[B].erase(st[B].find({a[i],-i}));
			}
		}
	}
}
int Push(int B, int l, int r, int x)
{
	BreakBlock(B);
	for(int i=l;i<=r;i++) if(a[i]>x) swap(a[i],x);
	BuildBlock(B,B*S,min((B+1)*S,n)-1);
	return x;
}
void BuildAll(){ for(int l=0;l<n;l+=S) BuildBlock(l/S,l,min(l+S,n)-1);}
int Query(int l, int r, int x)
{
	int L=l/S,R=r/S;
	if(L==R)
	{
		if(l==L*S && r==R*S+S-1) x=Push(L,x);
		else x=Push(L,l,r,x);
	}
	else
	{
		if(l==L*S) x=Push(L,x);
		else x=Push(L,l,L*S+S-1,x);
		for(int i=L+1;i<R;i++) x=Push(i,x);
		if(r==R*S+S-1) x=Push(R,x);
		else x=Push(R,R*S,r,x);
	}
	return x;
}
int main()
{
	scanf("%i %i",&n,&q);
	for(int i=0;i<n;i++) scanf("%i",&a[i]);
	BuildAll();
	while(q--)
	{
		int l,r,x;
		scanf("%i %i %i",&l,&r,&x);
		l--;r--;
		if(l<=r) x=Query(l,r,x);
		else x=Query(0,r,Query(l,n-1,x));
		printf("%i\n",x);
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:70:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%i",&a[i]);
                       ~~~~~^~~~~~~~~~~~
sushi.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&l,&r,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 632 KB Output is correct
2 Correct 137 ms 632 KB Output is correct
3 Runtime error 8 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12062 ms 21724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 632 KB Output is correct
2 Correct 137 ms 632 KB Output is correct
3 Runtime error 8 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -