| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 153412 |
2019-09-14T06:37:08 Z |
Mercenary |
Cake (CEOI14_cake) |
C++14 |
|
1562 ms |
7236 KB |
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 250000 + 5;
int n , q , a;
int d[maxn];
struct IT{
int s[maxn * 4] , lz[maxn * 4];
// int s1[maxn * 4];
void push(int x , bool key){
s[x] += lz[x];
if(key == 1){
lz[x * 2] += lz[x];
lz[x * 2 + 1] += lz[x];
}
lz[x] = 0;
}
void build(int x,int l , int r){
if(l == r){
s[x] = d[l];
return;
}
int mid = l + r >> 1;
build(x * 2 , l , mid);
build(x * 2 + 1 , mid + 1 , r);
s[x] = min(s[x * 2] , s[x * 2 + 1]);
}
void update(int x , int l , int r , int pos){
push(x , l != r);
if(l == r){
lz[x]--;
push(x , l != r);
return;
}
int mid = l + r >> 1;
if(mid >= pos)update(x * 2 , l , mid , pos);
else update(x * 2 + 1 , mid + 1 , r , pos);
s[x] = min(s[x * 2] , s[x * 2 + 1]);
}
void update(int x , int l , int r , int pos , int val){
push(x , l != r);
if(l == r){
if(l == pos)s[x] = val;
// cout << l << " " << pos << " " << s[x] << endl;
return;
}
int mid = l + r >> 1;
if(mid >= pos)update(x * 2 , l , mid , pos , val);
else update(x * 2 + 1 , mid + 1 , r , pos , val);
s[x] = min(s[x * 2] , s[x * 2 + 1]);
}
int query(int x , int l , int r , int L , int R){
push(x , l != r);
if(l > R || L > r){
return 1e9;
}
if(L <= l && r <= R){
// cout << l << " " << r << " " << s[x] << endl;
return s[x];
}
int mid = l + r >> 1;
return min(query(x * 2 , l , mid , L , R) , query(x * 2 + 1 , mid + 1 , r , L , R));
}
}s;
int top[12];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n >> a;
for(int i = 1 ; i <= n ; ++i)cin >> d[i];
for(int i = 1 ; i <= n ; ++i)d[i] = n - d[i] + 1;
// for(int i = 1 ; i <= n ; ++i)cout << d[i] << " ";cout << endl;
for(int i = 1 ; i <= n ; ++i){
if(d[i] <= 10)top[d[i]] = i;
}
s.build(1 , 1 , n);
cin >> q;
while(q--){
char type;cin >> type;
if(type == 'E'){
int i , e;cin >> i >> e;
s.lz[1]++;
int now = 11;
for(int j = 10 ; j >= 1 ; --j){
if(top[j] == i){
now = j;
}
}
for(int j = now ; j > e ; --j){
top[j] = top[j - 1];
}
for(int j = 1 ; j < e ; ++j){
// if(top[j] < a)l.update(1 , 1 , n , top[j]);
// else r.update(1 , a + 1 , n , top[j]);
s.update(1 , 1 , n , top[j]);
}
top[e] = i;
// if(i < a)l.update(1 , 1 , a - 1 , i , e);
// else if(i > a)r.update(1 , a + 1 , n , i , e);
s.update(1 , 1 , n , i , e);
// cerr << e << " " << i << endl;
// for(int j = 1 ; j <= 10 ; ++j){
// cerr << top[j] << " \n"[j == 10];
// }
}else{
int i;cin >> i;
if(i == a){
cout << 0 << '\n';
}else if(i < a){
int res = 0;
int need = s.query(1 , 1 , n , i , a - 1);
for(int i = 17 ; i >= 0 ; --i){
if(a + res + (1 << i) <= n && s.query(1 , a + 1 , n , a + res + 1 , a + res + (1 << i)) >= need)
res += (1 << i);
}
cout << res + a - i << '\n';
}else{
int res = 0;
int need = s.query(1 , 1 , n , a + 1 , i);
for(int i = 17 ; i >= 0 ; --i){
if(a - res - (1 << i) >= 1 && s.query(1 , 1 , n , a - res - (1 << i) , a - res - 1) >= need)
res += (1 << i);
}
cout << res + i - a << '\n';
}
}
}
}
Compilation message
cake.cpp: In member function 'void IT::build(int, int, int)':
cake.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake.cpp: In member function 'void IT::update(int, int, int, int)':
cake.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake.cpp: In member function 'void IT::update(int, int, int, int, int)':
cake.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake.cpp: In member function 'int IT::query(int, int, int, int, int)':
cake.cpp:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake.cpp: In function 'int main()':
cake.cpp:87:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:88:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT", "w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
688 KB |
Output isn't correct |
| 2 |
Incorrect |
171 ms |
692 KB |
Output isn't correct |
| 3 |
Incorrect |
191 ms |
760 KB |
Output isn't correct |
| 4 |
Incorrect |
140 ms |
700 KB |
Output isn't correct |
| 5 |
Incorrect |
281 ms |
888 KB |
Output isn't correct |
| 6 |
Incorrect |
246 ms |
888 KB |
Output isn't correct |
| 7 |
Incorrect |
214 ms |
888 KB |
Output isn't correct |
| 8 |
Incorrect |
149 ms |
1016 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
404 ms |
3564 KB |
Output isn't correct |
| 2 |
Incorrect |
358 ms |
3320 KB |
Output isn't correct |
| 3 |
Incorrect |
362 ms |
3460 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Incorrect |
440 ms |
6108 KB |
Output isn't correct |
| 6 |
Incorrect |
452 ms |
6300 KB |
Output isn't correct |
| 7 |
Incorrect |
446 ms |
6036 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
504 KB |
Output isn't correct |
| 2 |
Incorrect |
73 ms |
776 KB |
Output isn't correct |
| 3 |
Incorrect |
168 ms |
1784 KB |
Output isn't correct |
| 4 |
Incorrect |
189 ms |
1788 KB |
Output isn't correct |
| 5 |
Incorrect |
189 ms |
752 KB |
Output isn't correct |
| 6 |
Incorrect |
313 ms |
2196 KB |
Output isn't correct |
| 7 |
Incorrect |
272 ms |
1084 KB |
Output isn't correct |
| 8 |
Incorrect |
121 ms |
2976 KB |
Output isn't correct |
| 9 |
Incorrect |
1562 ms |
7236 KB |
Output isn't correct |
| 10 |
Incorrect |
616 ms |
1624 KB |
Output isn't correct |
| 11 |
Incorrect |
859 ms |
2440 KB |
Output isn't correct |
| 12 |
Incorrect |
1472 ms |
6996 KB |
Output isn't correct |
| 13 |
Incorrect |
1317 ms |
7208 KB |
Output isn't correct |
