oj.uz

답안 #110748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110748 2019-05-12T07:33:12 Z MAMBA 케이크 (CEOI14_cake) C++17
35 / 100
 1063 ms 35440 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 (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:162:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < R.size() && R[ptr].second > L[i].second) ptr++;
          ~~~~^~~~~~~~~~
cake.cpp:163: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 30 ms 31736 KB Output is correct
2 Correct 32 ms 31608 KB Output is correct
3 Correct 28 ms 31660 KB Output is correct
4 Incorrect 34 ms 31736 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 864 ms 31864 KB Output is correct
2 Correct 876 ms 31812 KB Output is correct
3 Correct 910 ms 31784 KB Output is correct
4 Correct 793 ms 31744 KB Output is correct
5 Correct 1063 ms 31864 KB Output is correct
6 Correct 964 ms 31872 KB Output is correct
7 Correct 923 ms 31864 KB Output is correct
8 Correct 860 ms 31992 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 33016 KB Output is correct
2 Correct 95 ms 32864 KB Output is correct
3 Correct 96 ms 32832 KB Output is correct
4 Correct 27 ms 31744 KB Output is correct
5 Correct 165 ms 34304 KB Output is correct
6 Correct 167 ms 34296 KB Output is correct
7 Correct 121 ms 34144 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 31824 KB Output isn't correct
2 Incorrect 108 ms 31864 KB Output isn't correct
3 Incorrect 168 ms 32336 KB Output isn't correct
4 Correct 168 ms 32248 KB Output is correct
5 Incorrect 193 ms 32048 KB Output isn't correct
6 Correct 290 ms 32632 KB Output is correct
7 Correct 264 ms 32248 KB Output is correct
8 Correct 592 ms 32632 KB Output is correct
9 Correct 1002 ms 35440 KB Output is correct
10 Incorrect 544 ms 32888 KB Output isn't correct
11 Correct 689 ms 33252 KB Output is correct
12 Correct 961 ms 35004 KB Output is correct
13 Correct 876 ms 35396 KB Output is correct