oj.uz

답안 #110744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110744 2019-05-12T07:27:53 Z MAMBA 케이크 (CEOI14_cake) C++17
35 / 100
 1298 ms 35432 KB 
#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 fun(int id, int E) {
	if (id == a) return;
	int pre = 12;
	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 > 11) {
			L.erase(L.begin() + i);
			break;
		}

	rep(i , 0 , R.size())
		if (R[i].second > 11) {
			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 - 11) {
			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

cake.cpp: In function 'int segGet(int, int, int, int)':
cake.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
cake.cpp: In function 'void segSmin(int, int, int, int, int, int)':
cake.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
cake.cpp: In function 'void segAssign(int, int, int, int, int, int)':
cake.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
cake.cpp: In function 'void fun(int, int)':
cake.cpp:156:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < R.size() && R[ptr].second > L[i].second) ptr++;
          ~~~~^~~~~~~~~~
cake.cpp:157: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 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 31744 KB Output is correct
2 Correct 28 ms 31744 KB Output is correct
3 Correct 30 ms 31608 KB Output is correct
4 Incorrect 31 ms 31608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 894 ms 31780 KB Output is correct
2 Correct 754 ms 31908 KB Output is correct
3 Correct 905 ms 31864 KB Output is correct
4 Correct 841 ms 31940 KB Output is correct
5 Correct 1298 ms 31864 KB Output is correct
6 Correct 1086 ms 31964 KB Output is correct
7 Correct 985 ms 31992 KB Output is correct
8 Correct 808 ms 31992 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 33068 KB Output is correct
2 Correct 94 ms 33004 KB Output is correct
3 Correct 77 ms 32872 KB Output is correct
4 Correct 32 ms 31708 KB Output is correct
5 Correct 146 ms 34524 KB Output is correct
6 Correct 155 ms 34552 KB Output is correct
7 Correct 121 ms 34076 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 31744 KB Output isn't correct
2 Incorrect 88 ms 31928 KB Output isn't correct
3 Incorrect 137 ms 32248 KB Output isn't correct
4 Correct 138 ms 32312 KB Output is correct
5 Incorrect 177 ms 31996 KB Output isn't correct
6 Correct 275 ms 32632 KB Output is correct
7 Correct 248 ms 32216 KB Output is correct
8 Correct 527 ms 32504 KB Output is correct
9 Correct 1181 ms 35412 KB Output is correct
10 Incorrect 579 ms 32888 KB Output isn't correct
11 Correct 737 ms 33448 KB Output is correct
12 Correct 935 ms 35092 KB Output is correct
13 Correct 839 ms 35432 KB Output is correct