| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 709221 |
2023-03-13T08:41:38 Z |
ktkerem |
Cake (CEOI14_cake) |
C++17 |
|
2000 ms |
13080 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];
struct segt{
std::vector<ll> valt;
void upd(ll l , ll r , ll nt , ll a , ll vl){
if(l == r){
//std::cout << l << " " << r << " " << a << std::endl;
valt[a] = vl;
return ;
}
ll md = (l + r)/2;
if(nt <= md){
upd(l , md , nt , a*2 , vl);
}
else{
upd(md+1 , r , nt , a*2+1 , vl);
}
valt[a] = std::max(valt[a*2] , valt[a*2+1]);
}
ll que(ll l , ll r , ll nl , ll nr , ll a){
if(nl > r || nr < l){
return 0;
}
if(nl >= l && nr <= r){
return valt[a];
}
ll md = (nl + nr)/2;
ll lf = que(l , r , nl , md , a*2) , rg = que(l , r , md+1 , nr , a*2+1);
return std::max(lf , rg);
}
};
segt a;
/**/
/*functions*/
void addgte(ll y , ll ind){
ll pl = std::min(10ll , n);
for(ll i = pl;y <= i;i--){
gt[i+1] = gt[i];
}
gt[y].sec = ind;
for(ll i = y;0<=i;i--){
gt[i].fi++;
a.upd(0 , n-1 , gt[i].sec , 1 , gt[i].fi);
}
/*for(ll i = 0;pl>i;i++){
std::cout << gt[i].fi << " " << gt[i].sec << "\n";
}*/
}
void delgte(ll y){
ll pl = std::min(10ll , n);
for(ll i = y;pl>i;i++){
gt[i] = gt[i-1];
}
gt[pl-1] = {0 , 0};
/*for(ll i = 0;pl>i;i++){
std::cout << gt[i].fi << " " << gt[i].sec << "\n";
}
std::cout << std::endl;*/
}
/**/
void solve(){
std::cin >> n >> k;
a.valt.resize(4*n+5);
k--;
ar.resize(n);
for(ll i = 0 ; n>i;i++){
std::cin >> ar[i].fi;
ar[i].sec = i;
a.upd(0 , n-1 , i , 1 , ar[i].fi);
}
std::sort(all(ar) , std::greater<llll>());
ll pl = std::min(10ll , n);
for(ll i = 0;pl>i;i++){
gt[i] = ar[i];
}
ll q;std::cin >> q;
while(q--){
std::string h;ll x , y;std::cin >> h >> x;x--;
if(h == "E"){
std::cin >> y;y--;
for(ll i = 0;pl>i;i++){
if(gt[i].sec == x){
delgte(i);
}
}
addgte(y , x);
}
else{
if(k == n-1){
std::cout << k - x;
}
else if(k == 0){
std::cout << x - k;
}
else if(x > k){
ll l = 0 , r = k-1;
ll o = a.que(k+1 , x , 0 , n-1 , 1);
while(r > l){
ll md = (l + r)/2;
ll s = a.que(md , k-1 , 0 , n-1 , 1);
if(s > o){
l = md+1;
}
else{
r = md;
}
}
ll ans = k - l;
if(a.que(l , k-1 , 0 , n-1 , 1) > o){
ans = 0;
}
ans += x - k;
std::cout << ans;
}
else if(k > x){
ll l = k+1 , r = n-1;
ll o = a.que(x , k-1 , 0 , n-1 , 1);
//std::cout << o << "\n";
while(r > l){
ll md = (l + r+1)/2;
ll s = a.que(k+1 , md , 0 , n-1 , 1);
if(s > o){
r = md-1;
}
else{
l = md;
}
}
ll ans = l - k;
if(a.que(k+1 , l , 0 , n-1 , 1) > o){
ans = 0;
}
ans += k - x;
std::cout << ans;
}
else{
std::cout << "0";
}
if(q){
std::cout << std::endl;
}
}
}
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:78: 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:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | freopen("in.txt" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | freopen("out.txt" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2059 ms |
12324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2070 ms |
12060 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2077 ms |
12396 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2079 ms |
12508 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2049 ms |
12256 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2069 ms |
12548 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2078 ms |
12976 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2021 ms |
12384 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2054 ms |
12992 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
13048 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2065 ms |
12528 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2066 ms |
12472 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2081 ms |
12724 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2067 ms |
12940 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2044 ms |
12892 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2066 ms |
12140 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
13080 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2060 ms |
12996 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2070 ms |
12148 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2064 ms |
12628 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2076 ms |
12796 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2083 ms |
12404 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2078 ms |
12776 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2076 ms |
12408 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2073 ms |
12816 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2070 ms |
12812 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2068 ms |
12612 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2057 ms |
13012 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2037 ms |
12152 KB |
Time limit exceeded |
