oj.uz

Submission #33331

# Submission time Handle Problem Language Result Execution time Memory
33331 2017-10-23T19:03:07 Z imaxblue Cake (CEOI14_cake) C++14
0 / 100
 1813 ms 23348 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 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=1; x=a[p];
                printf("%i\n", s-p+query(1, s+1, 0));
            } else {
                t=0; x=a[p];
                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:59: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:65:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", &a[l]);
                           ^
cake.cpp:69:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &q);
                    ^
cake.cpp:71: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:73: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 10808 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 959 ms 16484 KB Output isn't correct
2 Incorrect 396 ms 11732 KB Output isn't correct
3 Incorrect 506 ms 11336 KB Output isn't correct
4 Incorrect 306 ms 11336 KB Output isn't correct
5 Incorrect 1039 ms 17276 KB Output isn't correct
6 Incorrect 783 ms 17144 KB Output isn't correct
7 Incorrect 603 ms 11996 KB Output isn't correct
8 Incorrect 373 ms 11996 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 15560 KB Output isn't correct
2 Incorrect 106 ms 15560 KB Output isn't correct
3 Incorrect 99 ms 15560 KB Output isn't correct
4 Incorrect 0 ms 10808 KB Output isn't correct
5 Incorrect 416 ms 22556 KB Output isn't correct
6 Incorrect 373 ms 22556 KB Output isn't correct
7 Incorrect 193 ms 22556 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 10940 KB Output isn't correct
2 Incorrect 43 ms 11072 KB Output isn't correct
3 Incorrect 136 ms 13184 KB Output isn't correct
4 Incorrect 179 ms 13184 KB Output isn't correct
5 Incorrect 193 ms 10940 KB Output isn't correct
6 Incorrect 276 ms 13844 KB Output isn't correct
7 Incorrect 176 ms 11336 KB Output isn't correct
8 Incorrect 389 ms 15560 KB Output isn't correct
9 Incorrect 1813 ms 22556 KB Output isn't correct
10 Incorrect 669 ms 10940 KB Output isn't correct
11 Incorrect 949 ms 11732 KB Output isn't correct
12 Incorrect 1716 ms 20180 KB Output isn't correct
13 Incorrect 1273 ms 23348 KB Output isn't correct