oj.uz

답안 #110749

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110749 2019-05-12T07:35:00 Z MAMBA 케이크 (CEOI14_cake) C++17
100 / 100
 1066 ms 35472 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);
}

int shit;

inline void fun(int id, int E) {
	int pre = 12;
	if (id == a) pre = shit;
	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) {
		shit = E;
		return;
	}

	if (shit >= E && shit < pre)
		shit++;

	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];

	shit= n + 1 - p[a];

	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:164:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < R.size() && R[ptr].second > L[i].second) ptr++;
          ~~~~^~~~~~~~~~
cake.cpp:165: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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 29 ms 31688 KB Output is correct
3 Correct 29 ms 31736 KB Output is correct
4 Correct 33 ms 31644 KB Output is correct
5 Correct 43 ms 31736 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1020 ms 31864 KB Output is correct
2 Correct 782 ms 31884 KB Output is correct
3 Correct 1000 ms 31808 KB Output is correct
4 Correct 797 ms 31868 KB Output is correct
5 Correct 1066 ms 31864 KB Output is correct
6 Correct 890 ms 31992 KB Output is correct
7 Correct 943 ms 31996 KB Output is correct
8 Correct 941 ms 31964 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 33016 KB Output is correct
2 Correct 108 ms 32944 KB Output is correct
3 Correct 89 ms 32972 KB Output is correct
4 Correct 28 ms 31744 KB Output is correct
5 Correct 161 ms 34296 KB Output is correct
6 Correct 154 ms 34296 KB Output is correct
7 Correct 128 ms 34084 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 31768 KB Output is correct
2 Correct 91 ms 31888 KB Output is correct
3 Correct 176 ms 32248 KB Output is correct
4 Correct 134 ms 32240 KB Output is correct
5 Correct 173 ms 31964 KB Output is correct
6 Correct 363 ms 32728 KB Output is correct
7 Correct 276 ms 32292 KB Output is correct
8 Correct 569 ms 32504 KB Output is correct
9 Correct 1022 ms 35472 KB Output is correct
10 Correct 563 ms 32932 KB Output is correct
11 Correct 629 ms 33404 KB Output is correct
12 Correct 1058 ms 35044 KB Output is correct
13 Correct 806 ms 35272 KB Output is correct