| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110723 |
2019-05-12T06:50:08 Z |
MAMBA |
Wall (CEOI14_wall) |
C++17 |
|
464 ms |
35832 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], tmp[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];
memcpy(tmp, p, sizeof(p));
sort(tmp, tmp + a);
sort(tmp + a + 1 , tmp + n);
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;
rep(i , a + 1, n) {
smax(mx , p[i]);
arr[i] = lower_bound(tmp, tmp + a, mx) - tmp;
}
mx = -1;
for (int i = a - 1; ~i; i--) {
smax(mx , p[i]);
arr[i] = lower_bound(tmp + a + 1, tmp + n, mx) - (tmp + 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) << endl;
}
}
return 0;
}
Compilation message
wall.cpp: In function 'int segGet(int, int, int, int)':
wall.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
wall.cpp: In function 'void segSmin(int, int, int, int, int, int)':
wall.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
wall.cpp: In function 'void segAssign(int, int, int, int, int, int)':
wall.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
wall.cpp: In function 'void dfs(int, int, int)':
wall.cpp:110:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
wall.cpp: In function 'void fun(int, int)':
wall.cpp:184:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr < R.size() && R[ptr].second > L[i].second) ptr++;
~~~~^~~~~~~~~~
wall.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 |
Incorrect |
34 ms |
35704 KB |
Output isn't correct |
| 2 |
Runtime error |
417 ms |
24184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
37 ms |
35576 KB |
Output isn't correct |
| 4 |
Incorrect |
36 ms |
35576 KB |
Output isn't correct |
| 5 |
Incorrect |
29 ms |
35576 KB |
Output isn't correct |
| 6 |
Incorrect |
29 ms |
35584 KB |
Output isn't correct |
| 7 |
Incorrect |
30 ms |
35740 KB |
Output isn't correct |
| 8 |
Runtime error |
386 ms |
24032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Incorrect |
30 ms |
35584 KB |
Output isn't correct |
| 10 |
Incorrect |
29 ms |
35584 KB |
Output isn't correct |
| 11 |
Incorrect |
29 ms |
35580 KB |
Output isn't correct |
| 12 |
Runtime error |
379 ms |
23928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Incorrect |
34 ms |
35576 KB |
Output isn't correct |
| 14 |
Incorrect |
35 ms |
35548 KB |
Output isn't correct |
| 15 |
Incorrect |
31 ms |
35576 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
464 ms |
24036 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Incorrect |
32 ms |
35584 KB |
Output isn't correct |
| 3 |
Runtime error |
427 ms |
24028 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Incorrect |
31 ms |
35804 KB |
Output isn't correct |
| 5 |
Incorrect |
30 ms |
35576 KB |
Output isn't correct |
| 6 |
Incorrect |
30 ms |
35576 KB |
Output isn't correct |
| 7 |
Incorrect |
29 ms |
35584 KB |
Output isn't correct |
| 8 |
Runtime error |
427 ms |
24040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Incorrect |
32 ms |
35584 KB |
Output isn't correct |
| 10 |
Incorrect |
31 ms |
35584 KB |
Output isn't correct |
| 11 |
Incorrect |
29 ms |
35576 KB |
Output isn't correct |
| 12 |
Incorrect |
29 ms |
35832 KB |
Output isn't correct |
| 13 |
Incorrect |
31 ms |
35704 KB |
Output isn't correct |
| 14 |
Incorrect |
30 ms |
35548 KB |
Output isn't correct |
| 15 |
Incorrect |
34 ms |
35584 KB |
Output isn't correct |
| 16 |
Incorrect |
32 ms |
35576 KB |
Output isn't correct |
| 17 |
Incorrect |
32 ms |
35576 KB |
Output isn't correct |
| 18 |
Incorrect |
34 ms |
35576 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
35576 KB |
Output isn't correct |
| 2 |
Runtime error |
452 ms |
24024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
371 ms |
24056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Incorrect |
34 ms |
35580 KB |
Output isn't correct |
| 5 |
Runtime error |
410 ms |
24184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Incorrect |
33 ms |
35576 KB |
Output isn't correct |
| 7 |
Incorrect |
31 ms |
35576 KB |
Output isn't correct |
| 8 |
Runtime error |
328 ms |
24028 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Incorrect |
30 ms |
35584 KB |
Output isn't correct |
| 10 |
Runtime error |
403 ms |
24056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Incorrect |
35 ms |
35576 KB |
Output isn't correct |
| 12 |
Incorrect |
34 ms |
35576 KB |
Output isn't correct |
| 13 |
Incorrect |
31 ms |
35628 KB |
Output isn't correct |
| 14 |
Runtime error |
351 ms |
24056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Incorrect |
30 ms |
35576 KB |
Output isn't correct |
| 16 |
Incorrect |
34 ms |
35584 KB |
Output isn't correct |
| 17 |
Incorrect |
30 ms |
35584 KB |
Output isn't correct |
| 18 |
Incorrect |
30 ms |
35576 KB |
Output isn't correct |
| 19 |
Incorrect |
39 ms |
35576 KB |
Output isn't correct |
| 20 |
Runtime error |
424 ms |
24156 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
