oj.uz

답안 #110733

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

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

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1024 ms 31860 KB Output is correct
2 Correct 729 ms 31736 KB Output is correct
3 Correct 761 ms 31740 KB Output is correct
4 Correct 822 ms 31864 KB Output is correct
5 Correct 1078 ms 31900 KB Output is correct
6 Correct 939 ms 31992 KB Output is correct
7 Correct 952 ms 31872 KB Output is correct
8 Correct 816 ms 31964 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 33016 KB Output is correct
2 Correct 94 ms 33016 KB Output is correct
3 Correct 78 ms 32916 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 156 ms 34268 KB Output is correct
6 Correct 145 ms 34424 KB Output is correct
7 Correct 123 ms 34168 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 31948 KB Output isn't correct
2 Incorrect 96 ms 31864 KB Output isn't correct
3 Incorrect 153 ms 32248 KB Output isn't correct
4 Correct 205 ms 32252 KB Output is correct
5 Incorrect 192 ms 31992 KB Output isn't correct
6 Correct 261 ms 32632 KB Output is correct
7 Correct 331 ms 32336 KB Output is correct
8 Correct 473 ms 32504 KB Output is correct
9 Correct 928 ms 35292 KB Output is correct
10 Incorrect 513 ms 33016 KB Output isn't correct
11 Correct 662 ms 33412 KB Output is correct
12 Correct 888 ms 34936 KB Output is correct
13 Correct 766 ms 35372 KB Output is correct