| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 229954 |
2020-05-07T09:22:10 Z |
Ruxandra985 |
Cake (CEOI14_cake) |
C++14 |
|
381 ms |
18680 KB |
#include <bits/stdc++.h>
#define DIMN 250010
#define ADD 1
using namespace std;
long long v[DIMN] , w[20] , f[20] , aux[DIMN];
pair <long long , int> aint[4 * DIMN] , p[DIMN];
int n;
void build (int nod , int st , int dr){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = make_pair( v[st] , st );
return;
}
build (2 * nod , st , mid);
build (2 * nod + 1 , mid + 1 , dr);
aint[nod] = max(aint[2 * nod] , aint[2 * nod + 1]);
}
void update (int nod , int st , int dr , int poz , long long val){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = make_pair( val , st );
return;
}
if (poz <= mid)
update (2 * nod , st , mid , poz , val);
else update (2 * nod + 1 , mid + 1 , dr , poz , val);
aint[nod] = max(aint[2 * nod] , aint[2 * nod + 1]);
}
long long query_fixed (int nod , int st , int dr , int l , int r){
int mid = (st + dr)/2;
long long sol = 0;
if (l <= st && dr <= r){
return aint[nod].first;
}
if (l <= mid)
sol = max(sol , query_fixed (2 * nod , st , mid , l , r));
if (mid + 1 <= r)
sol = max(sol , query_fixed (2 * nod + 1 , mid + 1 , dr , l , r));
return sol;
}
int query_check (int nod , int st , int dr , long long val , int l , int r , int type){
int mid = (st + dr)/2;
int sol;
if (type == -1)
sol = n + 1;
else sol = 0;
if (l <= st && dr <= r){
/// vreau fie cel mai mare din interval cu valoarea > val
/// fie cel mai mic din interval cu aceeasi proprietate
if (st == dr){
if (aint[st].first > val){
return st; /// pozitie valida
}
else {
/// nu e pozitie valida :(
if (type == -1)
return n + 1;
else return 0;
}
}
if (type == -1){ /// il vreau pe cel mai mic
if (aint[2 * nod].first > val)
return query_check(2 * nod , st , mid , val , l , r , type);
else if (aint[2 * nod + 1].first > val)
return query_check (2 * nod + 1 , mid + 1 , dr , val , l , r , type);
else return n + 1; /// nu exista
}
else { /// il vreau pe cel mai mare
if (aint[2 * nod + 1].first > val)
return query_check(2 * nod + 1 , mid + 1 , dr , val , l , r , type);
else if (aint[2 * nod].first > val)
return query_check (2 * nod , st , mid , val , l , r , type);
else return 0; /// nu exista
}
}
if (l <= mid){
if (type == -1)
sol = min(sol , query_check (2 * nod , st , mid , val , l , r , type));
else sol = max(sol , query_check (2 * nod , st , mid , val , l , r , type));
}
if (mid + 1 <= r){
if (type == -1)
sol = min(sol , query_check (2 * nod + 1 , mid + 1 , dr , val , l , r , type));
else sol = max(sol , query_check (2 * nod + 1 , mid + 1 , dr , val , l , r , type));
}
return sol;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int a , q , i , sol , elem , idx , poz , j , x;
long long val;
char c;
fscanf (fin,"%d%d",&n,&a);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%lld",&v[i]);
p[i] = make_pair(v[i] , i);
}
sort (p + 1 , p + n + 1);
for (i = max(1 , n - 9) ; i <= n ; i++){
if (n >= 10)
p[i].first = 1000000000LL * (10 - (n - i));
else p[i].first = 1000000000LL * i;
v[p[i].second] = p[i].first;
}
for (i = 1 ; i <= n ; i++)
aux[i] = v[i];
build (1 , 1 , n);
sort (v + 1 , v + n + 1);
elem = 0;
for (i = max(1 , n - 9) ; i <= n ; i++)
w[++elem] = v[i];
//w[elem + 1] = (n + 1);
fscanf (fin,"%d\n",&q);
for (;q;q--){
c = fgetc(fin);
if (c == 'E'){
fscanf (fin,"%d%d\n",&idx,&poz);
f[poz]++;
/// elem idx va lua valoarea poz in ierarhie
/// elem ... poz = 1
/// elem - 1 ... poz = 2
j = elem - poz + 1; /// aia care trb inlocuita
if (w[j] == aux[poz])
continue; /// e la fel
val = 1LL * j * 1000000000 + f[poz];
for (i = 1 ; i < j ; i++)
w[i] = w[i + 1];
w[j] = val;
/// val e noua valoare
update ( 1 , 1 , n , idx , val );
aux[poz] = val;
}
else { /// query urile
fscanf (fin,"%d\n",&x);
if (a < x){
val = query_fixed (1 , 1 , n , a , x);
sol = x - a + 1 + a - query_check (1 , 1 , n , val , 1 , a - 1 , 1) - 1;
}
else if (a == x)
sol = 1;
else {
val = query_fixed (1 , 1 , n , x , a);
sol = a - x + 1 + query_check (1 , 1 , n , val , a + 1 , n , -1) - a - 1;
}
fprintf (fout,"%d\n", sol - 1);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:133:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&a);
~~~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:136:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld",&v[i]);
~~~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:162:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d\n",&q);
~~~~~~~^~~~~~~~~~~~~~~
cake.cpp:169:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d\n",&idx,&poz);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:200:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d\n",&x);
~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
1664 KB |
Output isn't correct |
| 2 |
Incorrect |
113 ms |
1664 KB |
Output isn't correct |
| 3 |
Incorrect |
117 ms |
1728 KB |
Output isn't correct |
| 4 |
Incorrect |
110 ms |
1664 KB |
Output isn't correct |
| 5 |
Incorrect |
125 ms |
2688 KB |
Output isn't correct |
| 6 |
Incorrect |
124 ms |
2688 KB |
Output isn't correct |
| 7 |
Incorrect |
124 ms |
2688 KB |
Output isn't correct |
| 8 |
Incorrect |
124 ms |
2808 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
8700 KB |
Output isn't correct |
| 2 |
Incorrect |
102 ms |
8696 KB |
Output isn't correct |
| 3 |
Incorrect |
103 ms |
8824 KB |
Output isn't correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
172 ms |
17528 KB |
Output isn't correct |
| 6 |
Incorrect |
179 ms |
17596 KB |
Output isn't correct |
| 7 |
Incorrect |
151 ms |
17688 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
1152 KB |
Output isn't correct |
| 2 |
Incorrect |
29 ms |
1280 KB |
Output isn't correct |
| 3 |
Incorrect |
63 ms |
4728 KB |
Output isn't correct |
| 4 |
Incorrect |
56 ms |
4732 KB |
Output isn't correct |
| 5 |
Incorrect |
65 ms |
1400 KB |
Output isn't correct |
| 6 |
Incorrect |
107 ms |
5624 KB |
Output isn't correct |
| 7 |
Incorrect |
98 ms |
2272 KB |
Output isn't correct |
| 8 |
Incorrect |
85 ms |
8064 KB |
Output isn't correct |
| 9 |
Incorrect |
373 ms |
18680 KB |
Output isn't correct |
| 10 |
Incorrect |
206 ms |
2296 KB |
Output isn't correct |
| 11 |
Incorrect |
234 ms |
3960 KB |
Output isn't correct |
| 12 |
Incorrect |
360 ms |
17144 KB |
Output isn't correct |
| 13 |
Incorrect |
381 ms |
18680 KB |
Output isn't correct |
