| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 708928 |
2023-03-12T17:44:42 Z |
ktkerem |
Cake (CEOI14_cake) |
C++17 |
|
519 ms |
35552 KB |
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 1e6;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll a , ll b){
return (rng() % (b-a+1)) + a;
}
/*global variables*/
ll n , k;
std::vector<llll> ar;
llll gt[15];
std::vector<llll> valt;
/**/
/*functions*/
void upd(ll nt , ll vl , ll l = 0 , ll r = n-1 , ll a = 1){
//std::cout << l << " " << r << std::endl;
if(l == r){
valt[a] = {vl , vl};
return;
}
ll md = (l + r)/2;
if(nt <= md){
upd(nt , vl , l , md , a*2);
}
else{
upd(nt , vl , md+1 , r , a*2+1);
}
valt[a] = {std::min(valt[a*2].fi , valt[a*2+1].fi) , std::max(valt[a*2].sec , valt[a*2+1].sec)};
}
llll que(ll l , ll r , ll nl = 0 , ll nr = n-1 , ll a = 1){
if(nl > r || nr < l){
return{limit , -limit};
}
if(l <= nl && r >= nr){
return valt[a];
}
ll md=(nl + nr)/2;
llll lf = que(l , r , nl , md , a*2);
llll rg = que(l , r , md+1 , nr , a*2+1);
return {std::min(lf.fi , rg.fi) , std::max(lf.sec , rg.sec)};
}
/**/
void solve(){
std::cin >> n >> k;k--;
valt.resize(4 * n + 5);
ll pl = std::min(n , 10ll);
ar.resize(n);
for(ll i = 0;n>i;i++){
std::cin >> ar[i].fi;
ar[i].sec = i;
if(i == k){
ar[i].fi = 0;
}
upd(i , ar[i].fi);
}
std::sort(all(ar) , std::greater<llll>());
for(ll i=0;pl>i;i++){
gt[i] = ar[i];
//std::cout << ar[i].fi << " " << ar[i].sec << "\n";
}
ll q;std::cin >> q;
while(q--){
//std::cout << std::endl;
std::string h;ll x;std::cin >> h >> x;x--;
if(h == "E"){
ll y;std::cin >> y;
y--;
if(x == k){
continue;
}
ll kd = 0;
for(ll i = 0;pl>i;i++){
if(gt[i].sec == x){
kd = 1;
}
if(kd){
gt[i] = gt[i+1];
}
}
//std::cout << kd << std::endl;
/*for(ll i = 0;pl>i;i++){
std::cout << gt[i].fi << " " << gt[i].sec << "\n";
}*/
//std::cout << "\n\n";
for(ll i = pl;i >= y;i--){
gt[i+1] = gt[i];
}
gt[y].sec = x;
for(ll i = 0;y>=i;i++){
gt[i].fi++;
upd(gt[i].sec , gt[i].fi);
}
/*for(ll i = 0;pl>i;i++){
std::cout << gt[i].fi << " " << gt[i].sec << "\n";
}*/
}
else{
if(k > x){
llll o = que(x , k);
//std::cout << o.fi << " " << o.sec << "\n";
ll l = k , r = n-1;
while(r > l){
ll md = (l + r + 1)/2;
llll sl = que(k , md);
//std::cout << k << " " << md << " " << sl.fi << " " << sl.sec << "\n";
if(o.sec < sl.sec){
r = md-1;
}
else{
l = md;
}
}
std::cout << l - k + k - x << "\n";
}
else if(k < x){
llll o = que(k , x);
ll l = 0 , r = k;
while(r > l){
ll md = (l + r)/2;
llll sl = que(md , k);
if(o.sec < sl.sec){
l = md + 1;
}
else{
r = md;
}
}
std::cout << k - l + x - k << "\n";
}
else{
std::cout << "0\n";
}
}
}
return;/**/
}
int main(){
std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("in.txt" , "r" , stdin);
freopen("out.txt" , "w" , stdout);
#endif
ll t = 1;
//std::cin >> t;
while(t--){
solve();
}
}
Compilation message
cake.cpp:5:82: warning: "/*" within comment [-Wcomment]
5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
|
cake.cpp: In function 'int main()':
cake.cpp:153:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | freopen("in.txt" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:154:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | freopen("out.txt" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
453 ms |
35280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
437 ms |
35380 KB |
Output isn't correct |
| 2 |
Incorrect |
463 ms |
35488 KB |
Output isn't correct |
| 3 |
Incorrect |
475 ms |
35376 KB |
Output isn't correct |
| 4 |
Incorrect |
452 ms |
35272 KB |
Output isn't correct |
| 5 |
Incorrect |
446 ms |
35552 KB |
Output isn't correct |
| 6 |
Incorrect |
448 ms |
35320 KB |
Output isn't correct |
| 7 |
Incorrect |
459 ms |
35464 KB |
Output isn't correct |
| 8 |
Incorrect |
457 ms |
35392 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
465 ms |
35472 KB |
Output isn't correct |
| 2 |
Incorrect |
455 ms |
35376 KB |
Output isn't correct |
| 3 |
Incorrect |
440 ms |
35380 KB |
Output isn't correct |
| 4 |
Incorrect |
453 ms |
35276 KB |
Output isn't correct |
| 5 |
Incorrect |
480 ms |
35324 KB |
Output isn't correct |
| 6 |
Incorrect |
440 ms |
35408 KB |
Output isn't correct |
| 7 |
Incorrect |
465 ms |
35288 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
478 ms |
35296 KB |
Output isn't correct |
| 2 |
Incorrect |
519 ms |
35320 KB |
Output isn't correct |
| 3 |
Incorrect |
437 ms |
35336 KB |
Output isn't correct |
| 4 |
Incorrect |
490 ms |
35376 KB |
Output isn't correct |
| 5 |
Incorrect |
453 ms |
35396 KB |
Output isn't correct |
| 6 |
Incorrect |
444 ms |
35468 KB |
Output isn't correct |
| 7 |
Incorrect |
500 ms |
35380 KB |
Output isn't correct |
| 8 |
Incorrect |
508 ms |
35300 KB |
Output isn't correct |
| 9 |
Incorrect |
453 ms |
35276 KB |
Output isn't correct |
| 10 |
Incorrect |
479 ms |
35352 KB |
Output isn't correct |
| 11 |
Incorrect |
436 ms |
35356 KB |
Output isn't correct |
| 12 |
Incorrect |
486 ms |
35476 KB |
Output isn't correct |
| 13 |
Incorrect |
446 ms |
35284 KB |
Output isn't correct |
