Submission #114115

#	Time	Username	Problem	Language	Result	Execution time	Memory
114115		dndhk	Cake (CEOI14_cake)	C++14	100 / 100	1688 ms	9200 KiB

cake

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 250000;

int N, C, Q;
int arr[MAX_N+1];
vector<int> v;

struct SEG{
	SEG(int l, int r, int mx) : l(l), r(r), mx(mx) {}
	int l, r;
	int mx;
};

vector<SEG> seg;

void init(int idx, int s, int e){
	if(s==e)	return;
	seg[idx].l = seg.size(); seg.pb({-1, -1, 0});
	seg[idx].r = seg.size(); seg.pb({-1, -1, 0});
	init(seg[idx].l, s, (s+e)/2);
	init(seg[idx].r, (s+e)/2+1, e);
}

void update(int idx, int s, int e, int x, int y){
	if(s==e){
		seg[idx].mx = y;
		return;
	}
	if(x<=(s+e)/2){
		update(seg[idx].l, s, (s+e)/2, x, y);
	}else{
		update(seg[idx].r, (s+e)/2+1, e, x, y);
	}
	seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
}

int max(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y)	return seg[idx].mx;
	if(x>e || s>y)	return 0;
	return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}

int ans(int x){
	if(C==x)	return 0;
	if(x>C){
		int t = max(0, 1, N, C+1, x);
		int s = 1, e = C, m;
		while(s<e){
			m = (s+e)/2;
			if(max(0, 1, N, m, C-1)>t){
				s = m+1;
			}else{
				e = m;
			}
		}
		return x - s;
	}else{
		int t = max(0, 1, N, x, C-1);
		//cout<<t<<endl;
		int s = C, e = N, m;
		while(s<e){
			m = (s+e)/2+1;
			if(max(0, 1, N, C+1, m)>t){
				e = m-1;
			}else{
				s = m;
			}
		}
		return s - x;
	}
}

int maxarr;

void change(int x, int y){
	y--;
	int idx = -1;
	for(int i=0; i<v.size(); i++){
		if(v[i]==x){
			idx = i;
			break;
		}
	}
	if(idx==-1){
		for(int i=v.size(); i>=y+1; i--){
			v[i] = v[i-1];
		}
		v[y] = x;
	}else{
		for(int j=idx; j>=y+1; j--){
			v[j] = v[j-1];
		}
		v[y] = x;
	}
	for(int i=0; i<v.size(); i++){
		update(0, 1, N, v[i], maxarr+10-i);
	}
	maxarr += 10;
}


int main(){
	seg.pb({-1, -1, 0});
	scanf("%d%d", &N, &C);
	init(0, 1, N);
	maxarr = N;
	for(int i=1; i<=N; i++){
		scanf("%d", &arr[i]);
		update(0, 1, N, i, arr[i]);
	}
	for(int i=N; i>=max(1, N-9); i--){
		for(int j=1; j<=N; j++){
			if(arr[j]==i){
				v.pb(j);
				break;
			}
		}
	}
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		getchar();
		char c;
		scanf("%c", &c);
		if(c=='F'){
			int x;
			scanf("%d", &x);
			printf("%d\n", ans(x));
		}else{
			int x, y;
			scanf("%d%d", &x, &y);
			change(x, y);
		}
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In function 'void change(int, int)':
cake.cpp:100:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
cake.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &C);
  ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
cake.cpp:148:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
cake.cpp:152:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &x, &y);
    ~~~~~^~~~~~~~~~~~~~~~

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