oj.uz

Submission #33333

# Submission time Handle Problem Language Result Execution time Memory
33333 2017-10-24T00:08:57 Z imaxblue Cake (CEOI14_cake) C++14
0 / 100
 1853 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; 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 943 ms 16488 KB Output isn't correct
2 Incorrect 373 ms 11736 KB Output isn't correct
3 Incorrect 553 ms 11340 KB Output isn't correct
4 Incorrect 303 ms 11340 KB Output isn't correct
5 Incorrect 1006 ms 17280 KB Output isn't correct
6 Incorrect 753 ms 17148 KB Output isn't correct
7 Incorrect 566 ms 12000 KB Output isn't correct
8 Incorrect 353 ms 12000 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 15564 KB Output isn't correct
2 Incorrect 106 ms 15564 KB Output isn't correct
3 Incorrect 103 ms 15564 KB Output isn't correct
4 Incorrect 0 ms 10812 KB Output isn't correct
5 Incorrect 366 ms 22560 KB Output isn't correct
6 Incorrect 416 ms 22560 KB Output isn't correct
7 Incorrect 216 ms 22560 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 10944 KB Output isn't correct
2 Incorrect 53 ms 11076 KB Output isn't correct
3 Incorrect 136 ms 13188 KB Output isn't correct
4 Incorrect 179 ms 13188 KB Output isn't correct
5 Incorrect 196 ms 10944 KB Output isn't correct
6 Incorrect 276 ms 13848 KB Output isn't correct
7 Incorrect 193 ms 11340 KB Output isn't correct
8 Incorrect 403 ms 15564 KB Output isn't correct
9 Incorrect 1853 ms 22560 KB Output isn't correct
10 Incorrect 706 ms 10944 KB Output isn't correct
11 Incorrect 993 ms 11736 KB Output isn't correct
12 Incorrect 1719 ms 20184 KB Output isn't correct
13 Incorrect 1163 ms 23352 KB Output isn't correct