| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110733 |
2019-05-12T07:06:48 Z |
MAMBA |
Cake (CEOI14_cake) |
C++17 |
|
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);
~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
