oj.uz

Submission #33334

# Submission time Handle Problem Language Result Execution time Memory
33334 2017-10-24T00:16:04 Z imaxblue Cake (CEOI14_cake) C++14
0 / 100
 1906 ms 23352 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, s, q, gl, gr, t, k, x, p, z;
int seg[2][1000005], a[250005];
char ch;
vector<int> v;
map<int, int> r; map<int, int>::iterator i;
void up(int L, int R, int N){
    if (L>gl || R<gl) return;
    if (L==R){
        seg[t][N]=x;
        return;
    }
    up(lseg); up(rseg);
    seg[t][N]=max(seg[t][N*2+1], seg[t][N*2+2]);
}
int query(int L, int R, int N){
    if (L==R){
        return L-1;
    }
    if (seg[t][N*2+1]>x) query(lseg);
    else query(rseg);
}
void change(int P){
    if (P<s){
        gl=s-P; x=a[P]; t=0;
        up(1, s+1, 0);
    }
    if (P>s){
        gl=P-s; x=a[P]; t=1;
        up(1, n-s, 0);
    }
}
int hi(int L, int R, int N){
    if (L>gr) return 0;
    if (R<=gr) return seg[t][N];
    return max(hi(lseg), hi(rseg));
}
int main(){
    scanf("%i%i",&n, &s); --s;
    gl=s+1; x=(1 << 30); t=0;
    up(1, s+1, 0);
    gl=n-s; x=(1 << 30); t=1;
    up(1, n-s, 0);
    fox(l, n){
        scanf("%i", &a[l]);
        change(l);
        r[a[l]]=l;
    }
    scanf("%i", &q);
    fox(l, q){
        scanf(" %c%i", &ch, &p); --p;
        if (ch=='E'){
            scanf("%i", &z);
            r.erase(a[p]);
            i=r.end();
            fox(l, z) --i;
            k=a[p]=i->x+1;
            change(p);
            //cout << "*" << k << endl;
            //continue;
            v.clear();
            for (++i, ++k; i!=r.end(); ++i, ++k){
                a[i->y]=k;
                change(i->y);
                v.pb(i->y);
                //cout << "*";
            }
            fox(l, z-1){
                //cout << z << ' ' << v[l] << ' ';
                r.erase(a[v[l]]);
                r[a[v[l]]]=v[l];
            }
            r[a[p]]=p;
        } else {
            if (p==s){
                printf("0\n");
            } else if (p<s){
                t=0; gr=s-p; x=hi(1, n-s, 0);
                //cout << x << "*";
                t=1;
                printf("%i\n", s-p+query(1, s+1, 0));
            } else {
                t=1; gr=p-s; x=hi(1, s+1, 0);
                t=0;
                printf("%i\n", p-s+query(1, n-s, 0));

            }
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int query(int, int, int)':
cake.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
cake.cpp: In function 'int main()':
cake.cpp:64:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n, &s); --s;
                         ^
cake.cpp:70:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", &a[l]);
                           ^
cake.cpp:74:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &q);
                    ^
cake.cpp:76:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%i", &ch, &p); --p;
                                ^
cake.cpp:78:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i", &z);
                            ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 10812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 973 ms 16488 KB Output isn't correct
2 Incorrect 369 ms 11736 KB Output isn't correct
3 Incorrect 526 ms 11340 KB Output isn't correct
4 Incorrect 313 ms 11340 KB Output isn't correct
5 Incorrect 1043 ms 17280 KB Output isn't correct
6 Incorrect 786 ms 17148 KB Output isn't correct
7 Incorrect 619 ms 12000 KB Output isn't correct
8 Incorrect 356 ms 12000 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 15564 KB Output isn't correct
2 Incorrect 119 ms 15564 KB Output isn't correct
3 Incorrect 113 ms 15564 KB Output isn't correct
4 Incorrect 0 ms 10812 KB Output isn't correct
5 Incorrect 473 ms 22560 KB Output isn't correct
6 Incorrect 433 ms 22560 KB Output isn't correct
7 Incorrect 196 ms 22560 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 10944 KB Output isn't correct
2 Incorrect 59 ms 11076 KB Output isn't correct
3 Incorrect 163 ms 13188 KB Output isn't correct
4 Incorrect 173 ms 13188 KB Output isn't correct
5 Incorrect 199 ms 10944 KB Output isn't correct
6 Incorrect 273 ms 13848 KB Output isn't correct
7 Incorrect 196 ms 11340 KB Output isn't correct
8 Incorrect 433 ms 15564 KB Output isn't correct
9 Incorrect 1906 ms 22560 KB Output isn't correct
10 Incorrect 683 ms 10944 KB Output isn't correct
11 Incorrect 1018 ms 11736 KB Output isn't correct
12 Incorrect 1646 ms 20184 KB Output isn't correct
13 Incorrect 1283 ms 23352 KB Output isn't correct