Submission #110730

#	Time	Username	Problem	Language	Result	Execution time	Memory
110730		MAMBA	Wall (CEOI14_wall)	C++17	0 / 100	35 ms	31864 KiB

wall

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define for_all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1e6 + 10;

constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

ll po(ll v, ll u) { return u ? po(v * v % MOD , u >> 1) * (u & 1 ? v : 1) % MOD : 1; }

int n, a, p[N], arr[N];
int sega[N << 2] , segm[N << 2];
vector<pii> L , R;

inline void shift(int id) {
	if (~sega[id]) {
		sega[id << 1] = sega[id << 1 | 1] = sega[id];
		sega[id] = -1;
		segm[id << 1] = segm[id << 1 | 1] = 1e9;
	}
	smin(segm[id << 1] , segm[id]);
	smin(segm[id << 1 | 1] , segm[id]);
	segm[id] = 1e9;
}


int segGet(int pos, int l = 0, int r = n, int id = 1) {
	if (l == r - 1) {
		smin(sega[id] , segm[id]);
		return sega[id];
	}
	int mid = l + r >> 1;
	shift(id);
	if (pos < mid) 
		return segGet(pos , l , mid , id << 1 );
	return segGet(pos , mid ,r  ,id << 1| 1);
}

void segSmin(int s, int t, int val , int l = 0 , int r = n, int id = 1) {
	if (l >= s && r <= t) {
		smin(segm[id] , val);
		return;
	}
	if (l >= t || r <= s) return;
	shift(id);
	int mid = l + r >> 1;
	segSmin(s  ,t , val , l , mid , id << 1);
	segSmin(s , t , val, mid, r, id << 1 | 1);


}

void segAssign(int s, int t, int val, int l = 0, int r = n, int id = 1) {
	if (l >= s && r <= t) {
		segm[id] = 1e9;
		sega[id] = val;
		return;
	}
	if (r <= s || l >= t) 
		return;
	shift(id);
	int mid = l + r >> 1;
	segAssign(s , t , val, l, mid, id << 1);
	segAssign(s , t , val, mid, r, id << 1 | 1);
}

inline void DEBUG() {
	cout << "DEBUGING ......................" << endl;
	cout << "L :" << endl;
	for (auto e : L)
		cout << "	" << e.first << "->" << e.second << endl;
	cout << "R :" << endl;;
	for (auto e : R)
		cout << "	" << e.first << "->" << e.second << endl;
}

void dfs(int l = 0 , int r = n, int id = 1) {
	cout << l << ' ' << r << ' '<< sega[id] << ' '<< segm[id] << endl;
	if (l == r - 1) return;
	int mid = l + r >> 1;
	dfs(l  ,mid , id << 1);
	dfs(mid , r ,id << 1 | 1);
}

inline void DEBUG2() {
	cout << " /////////////////////////////// " << endl;
	rep(i , 0 , n)
		cout << segGet(i) << ' ';
	cout << endl;
}

inline void fun(int id, int E) {



	if (id == a) return;
	int pre = 11;
	rep(i , 0 , L.size())
		if (L[i].first == id) {
			pre = L[i].second;
			L.erase(L.begin() + i);
			break;
		}
	rep(i , 0 , R.size())
		if (R[i].first == id) {
			pre = R[i].second;
			R.erase(R.begin() + i);
			break;
		}


	for (auto &e : L) 
		if (e.second >= E && e.second < pre)
			e.second++;

	for (auto &e : R) 
		if (e.second >= E && e.second < pre)
			e.second++;

	rep(i , 0 , L.size())
		if (L[i].second > 10) {
			L.erase(L.begin() + i);
			break;
		}

	rep(i , 0 , R.size())
		if (R[i].second > 10) {
			R.erase(R.begin() + i);
			break;
		}



	if (id < a) {
		L.pb({id , E});
		for (int i = L.size() - 2; ~i; i--)
			if (L[i].first > L[i + 1].first)
				swap(L[i] , L[i + 1]);
	}
	else {
		R.pb({id , E});
		for (int i = R.size() - 2; ~i; i--)
			if (R[i].first > R[i + 1].first)
				swap(R[i] , R[i + 1]);
	}


	if (R.size())
		segSmin(0 , a , R[0].first - a - 1);
	if (L.size())
		segSmin(a + 1 , n , a - L.back().first - 1);



	int ptr = 0;
	for (int i = L.size() - 1; ~i; i--) {
		while (ptr < R.size() && R[ptr].second > L[i].second) ptr++;
		segAssign(0 , L[i].first + 1 , (ptr < R.size() ? R[ptr].first : n) - a - 1);
	}

	ptr = L.size() - 1;
	for (auto e : R) {
		while (~ptr && L[ptr].second > e.second ) ptr--;
		segAssign(e.first, n , a - 1 - (~ptr ? L[ptr].first : -1));
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

#ifndef LOCAL
	//	fileIO("forbidden1");
#endif

	cin >> n >> a;
	a--;
	rep(i , 0 , n) 
		cin >> p[i];

	rep(i , 0 , n)
		if (p[i] > n - 10) {
			if (i < a)
				L.pb({i , n - p[i] + 1});
			if (i > a)
				R.pb({i , n - p[i] + 1});
		}

	int mx = -1;
	int ptr = a - 1;
	rep(i , a + 1, n) {
		smax(mx , p[i]);
		while (~ptr && p[ptr] < mx) ptr--;
		arr[i] = a - ptr - 1;
	}
	mx = -1;
	ptr = a + 1;
	for (int i = a - 1; ~i; i--) {
		smax(mx , p[i]);
		while (ptr < n && p[ptr] < mx) ptr++;
		arr[i] = ptr - a - 1;
	}

	memset(sega , -1 , sizeof(sega));
	memset(segm , 63 , sizeof(segm));
	rep(i , 0 , n)
		segAssign(i , i + 1 , arr[i]);

	int Q;

	cin >> Q;

	rep(q , 0 , Q) {
		char tp; cin >> tp;
		if (tp == 'E') {
			int id, e;
			cin >> id >> e;
			id--;
			fun(id , e);
		}
		else {
			int id;
			cin >> id;
			id--;
			cout << segGet(id) + abs(a - id) << '\n';
		}
	}

	return 0;
}

Compilation message (stderr)

wall.cpp: In function 'int segGet(int, int, int, int)':
wall.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void segSmin(int, int, int, int, int, int)':
wall.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void segAssign(int, int, int, int, int, int)':
wall.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void dfs(int, int, int)':
wall.cpp:107:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void fun(int, int)':
wall.cpp:184:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < R.size() && R[ptr].second > L[i].second) ptr++;
          ~~~~^~~~~~~~~~
wall.cpp:185:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   segAssign(0 , L[i].first + 1 , (ptr < R.size() ? R[ptr].first : n) - a - 1);
                                   ~~~~^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40