| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110746 |
2019-05-12T07:30:33 Z |
MAMBA |
Cake (CEOI14_cake) |
C++17 |
|
1037 ms |
35580 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) {
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) 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];
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);
~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
31616 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31744 KB |
Output is correct |
| 3 |
Correct |
29 ms |
31608 KB |
Output is correct |
| 4 |
Correct |
35 ms |
31616 KB |
Output is correct |
| 5 |
Correct |
43 ms |
31736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
982 ms |
31864 KB |
Output is correct |
| 2 |
Correct |
809 ms |
31796 KB |
Output is correct |
| 3 |
Correct |
900 ms |
31864 KB |
Output is correct |
| 4 |
Correct |
933 ms |
31992 KB |
Output is correct |
| 5 |
Correct |
969 ms |
31992 KB |
Output is correct |
| 6 |
Correct |
958 ms |
31872 KB |
Output is correct |
| 7 |
Correct |
1037 ms |
31992 KB |
Output is correct |
| 8 |
Correct |
947 ms |
31992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
33004 KB |
Output is correct |
| 2 |
Correct |
88 ms |
32924 KB |
Output is correct |
| 3 |
Correct |
77 ms |
32856 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
31708 KB |
Output isn't correct |
| 5 |
Correct |
156 ms |
34428 KB |
Output is correct |
| 6 |
Correct |
133 ms |
34296 KB |
Output is correct |
| 7 |
Correct |
148 ms |
34200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
31864 KB |
Output is correct |
| 2 |
Correct |
101 ms |
31824 KB |
Output is correct |
| 3 |
Correct |
187 ms |
32376 KB |
Output is correct |
| 4 |
Correct |
162 ms |
32248 KB |
Output is correct |
| 5 |
Correct |
165 ms |
31992 KB |
Output is correct |
| 6 |
Correct |
262 ms |
32632 KB |
Output is correct |
| 7 |
Correct |
258 ms |
32376 KB |
Output is correct |
| 8 |
Correct |
556 ms |
32504 KB |
Output is correct |
| 9 |
Correct |
915 ms |
35580 KB |
Output is correct |
| 10 |
Correct |
560 ms |
32892 KB |
Output is correct |
| 11 |
Correct |
662 ms |
33244 KB |
Output is correct |
| 12 |
Correct |
932 ms |
34988 KB |
Output is correct |
| 13 |
Correct |
906 ms |
35424 KB |
Output is correct |
