Submission #1144109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144109		dpsaveslives	Cake (CEOI14_cake)	C++20	0 / 100	319 ms	10096 KiB

cake

#include<bits/stdc++.h>
using namespace std;
const int Len = 2.5e5 + 5;
struct node
{
	int val,idx;
}d[Len];
bool cmp(node x,node y){return x.val > y.val;}
int Id[Len],n,a,q,ans[Len << 2][2],rk[Len];
int ls(int x){return x << 1;}
int rs(int x){return x << 1 | 1;}
void push_up(int x,int t){ans[x][t] = min(ans[ls(x)][t] , ans[rs(x)][t]);}
void build(int p,int l,int r,int t)
{
	if(l == r)
	{
		ans[p][t] = d[l].val;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(p) , l , mid , t);
	build(rs(p) , mid + 1 , r , t);
	push_up(p , t);
}
void update(int p,int l,int r,int idx,int w,int t)
{
	if(l == r)
	{
		ans[p][t] = w;
		return;
	}
	int mid = (l + r) >> 1;
	if(idx <= mid) update(ls(p) , l , mid , idx , w , t);
	else update(rs(p) , mid + 1 , r , idx , w , t);
	push_up(p , t);
}
int query(int p,int l,int r,int nl,int nr,int t)
{
	if(nl <= l && nr >= r) return ans[p][t];
	int mid = (l + r) >> 1 , res = 1e9;
	if(nl <= mid) res = min(res , query(ls(p) , l , mid , nl , nr , t));
	if(nr > mid) res = min(res , query(rs(p) , mid + 1 , r , nl , nr , t));
	return res;
}
int find_l(int p,int l,int r,int fd)
{
	if(ans[p][0] > fd) return l - 1;//找不到
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(ans[rs(p)][0] < fd) return find_l(rs(p) , mid + 1 , r , fd);
	else return find_l(ls(p) , l , mid , fd);
}
int find_r(int p,int l,int r,int fd)
{
	if(ans[p][1] > fd) return r + 1;
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(ans[ls(p)][1] < fd) return find_r(ls(p) , l , mid , fd);
	else return find_r(rs(p) , mid + 1 , r , fd);
}
char s[5];
int main()
{
	scanf("%d %d",&n,&a);
	for(int i = 1 ; i <= n ; i ++)
	{
		scanf("%d",&d[i].val);
		d[i].val = n - d[i].val + 1;
		d[i].idx = i;
	}
	if(a != 1) build(1 , 1 , a - 1 , 0);
	if(a != n) build(1 , a + 1 , n , 1);
	sort(d + 1 , d + 1 + n , cmp);
	for(int i = 1 ; i <= n ; i ++) rk[i] = d[i].idx , Id[d[i].idx] = i;
	scanf("%d",&q);
	int nowminrk = 1;
	while(q --)
	{
		scanf("%s",s + 1);
		if(s[1] == 'F')
		{
			int x;scanf("%d",&x);
			if(x == a) printf("0\n");
			else if(x > a)
			{
				if(a == 1){printf("%d\n",x - 1);continue;}
				int Minn = query(1 , a + 1 , n , a + 1 , x , 1) ,
				Pos = a - 1 - find_l(1 , 1 , a - 1 , Minn);
				printf("%d\n",Pos + x - a);
			}
			else
			{
				if(a == n){printf("%d\n",a - x);continue;}
				int Minn = query(1 , 1 , a - 1 , x , a - 1 , 0) ,
				Pos = find_r(1 , a + 1 , n , Minn) - a - 1;
				printf("%d\n",Pos + a - x);
			}
		}
		else
		{
			int x,y,nowp = min(n , 10);scanf("%d %d",&x,&y);
			for(int i = 1 ; i <= min(n , 10) ; i ++) if(rk[i] == x) nowp = i;
			for(int i = nowp - 1 ; i >= y ; i --) rk[i + 1] = rk[i];
			rk[y] = x;
			for(int i = y ; i >= 1 ; i --)
			{
				nowminrk --;
				if(rk[i] > a) update(1 , a + 1 , n , rk[i] , nowminrk , 1);
				else if(rk[i] < a) update(1 , 1 , a - 1 , rk[i] , nowminrk , 0);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d %d",&n,&a);
      |         ~~~~~^~~~~~~~~~~~~~~
cake.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                 scanf("%d",&d[i].val);
      |                 ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d",&q);
      |         ~~~~~^~~~~~~~~
cake.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 scanf("%s",s + 1);
      |                 ~~~~~^~~~~~~~~~~~
cake.cpp:82:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |                         int x;scanf("%d",&x);
      |                               ~~~~~^~~~~~~~~
cake.cpp:101:57: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                         int x,y,nowp = min(n , 10);scanf("%d %d",&x,&y);
      |                                                    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50