oj.uz

Submission #33335

# Submission time Handle Problem Language Result Execution time Memory
33335 2017-10-24T00:47:26 Z imaxblue Cake (CEOI14_cake) C++14
50.8333 / 100
 1783 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 {
            //cout << p << ' ' << s << ' ';
            if (p==s){
                printf("0\n");
            } else if (p<s){
                t=0; gr=s-p; x=hi(1, s+1, 0);
                //cout << x << "*";
                t=1;
                printf("%i\n", s-p+query(1, n-s, 0));
            } else {
                t=1; gr=p-s; x=hi(1, n-s, 0);
                t=0;
                //cout << x << ' ';
                printf("%i\n", p-s+query(1, s+1, 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 Correct 0 ms 10812 KB Output is correct
2 Incorrect 0 ms 10812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 16488 KB Output is correct
2 Correct 383 ms 11736 KB Output is correct
3 Correct 509 ms 11340 KB Output is correct
4 Correct 316 ms 11340 KB Output is correct
5 Incorrect 1002 ms 17280 KB Output isn't correct
6 Incorrect 739 ms 17148 KB Output isn't correct
7 Correct 596 ms 12000 KB Output is correct
8 Correct 333 ms 12000 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 15564 KB Output is correct
2 Correct 116 ms 15564 KB Output is correct
3 Correct 99 ms 15564 KB Output is correct
4 Correct 0 ms 10812 KB Output is correct
5 Correct 373 ms 22560 KB Output is correct
6 Incorrect 353 ms 22560 KB Output isn't correct
7 Correct 203 ms 22560 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 10944 KB Output is correct
2 Correct 53 ms 11076 KB Output is correct
3 Correct 139 ms 13188 KB Output is correct
4 Correct 173 ms 13188 KB Output is correct
5 Correct 189 ms 10944 KB Output is correct
6 Correct 249 ms 13848 KB Output is correct
7 Correct 186 ms 11340 KB Output is correct
8 Correct 386 ms 15564 KB Output is correct
9 Correct 1783 ms 22560 KB Output is correct
10 Incorrect 703 ms 10944 KB Output isn't correct
11 Correct 993 ms 11736 KB Output is correct
12 Correct 1716 ms 20184 KB Output is correct
13 Incorrect 1253 ms 23352 KB Output isn't correct