oj.uz

Submission #78662

# Submission time Handle Problem Language Result Execution time Memory
78662 2018-10-06T21:52:50 Z duality Cake (CEOI14_cake) C++11
83.3333 / 100
 2000 ms 19080 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int d[250000];
set<pii,greater<pii> > S;
int tree[1 << 19];
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = d[s];
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(build(s,mid,2*i+1),build(mid+1,e,2*i+2));
    return tree[i];
}
int update(int s,int e,int ai,int i,int num) {
    if ((s > ai) || (e < ai)) return tree[i];
    else if (s == e) {
        tree[i] = d[s] = num;
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(update(s,mid,ai,2*i+1,num),update(mid+1,e,ai,2*i+2,num));
    return tree[i];
}
int query(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return 0;
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
int main() {
    int i,j;
    int N,Q,a;
    char c;
    int p,e,b;
    scanf("%d %d",&N,&a),a--;
    for (i = 0; i < N; i++) scanf("%d",&d[i]),S.insert(mp(d[i],i));
    scanf("%d",&Q);
    build(0,N-1,0);
    for (i = 0; i < Q; i++) {
        scanf(" %c",&c);
        if (c == 'E') {
            scanf("%d %d",&p,&e),p--;
            vpii v;
            for (j = 0; j < e-1; j++) v.pb(*S.begin()),S.erase(S.begin());
            S.erase(mp(d[p],p));
            update(0,N-1,p,0,(e == 1) ? N+i+1:v.back().first);
            S.insert(mp(d[p],p));
            for (j = 0; j < v.size(); j++) update(0,N-1,v[j].second,0,v[j].first+1),S.insert(mp(v[j].first+1,v[j].second));
        }
        else {
            scanf("%d",&b),b--;
            int xxx = 0;
            if (a == b) printf("0\n");
            else if (a < b) {
                int x = query(0,N-1,a+1,b,0);
                int l = 0,r = a;
                while (l < r) {
                    int m = (l+r) / 2;
                    if (query(0,N-1,m,a-1,0) <= x) r = m;
                    else l = m+1;
                }
                printf("%d\n",b-l),xxx = b-l;
            }
            else {
                int x = query(0,N-1,b,a-1,0);
                int l = a,r = N-1;
                while (l < r) {
                    int m = (l+r+1) / 2;
                    if (query(0,N-1,a+1,m,0) <= x) l = m;
                    else r = m-1;
                }
                printf("%d\n",l-b),xxx = l-b;
            }
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:107:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < v.size(); j++) update(0,N-1,v[j].second,0,v[j].first+1),S.insert(mp(v[j].first+1,v[j].second));
                         ~~^~~~~~~~~~
cake.cpp:111:17: warning: variable 'xxx' set but not used [-Wunused-but-set-variable]
             int xxx = 0;
                 ^~~
cake.cpp:94:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&a),a--;
     ~~~~~~~~~~~~~~~~~~~~^~~~
cake.cpp:95:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&d[i]),S.insert(mp(d[i],i));
                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
     ~~~~~^~~~~~~~~
cake.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&c);
         ~~~~~^~~~~~~~~~
cake.cpp:101:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&p,&e),p--;
             ~~~~~~~~~~~~~~~~~~~~^~~~
cake.cpp:110:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b),b--;
             ~~~~~~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 11 ms 612 KB Output is correct
5 Correct 31 ms 1180 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 1192 KB Output is correct
2 Correct 442 ms 1204 KB Output is correct
3 Correct 531 ms 1204 KB Output is correct
4 Correct 300 ms 1232 KB Output is correct
5 Correct 871 ms 2128 KB Output is correct
6 Correct 731 ms 2256 KB Output is correct
7 Correct 626 ms 2256 KB Output is correct
8 Correct 357 ms 2256 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 7336 KB Output is correct
2 Correct 307 ms 7336 KB Output is correct
3 Correct 315 ms 7336 KB Output is correct
4 Correct 2 ms 7336 KB Output is correct
5 Correct 603 ms 16172 KB Output is correct
6 Correct 683 ms 16176 KB Output is correct
7 Correct 734 ms 16176 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 16176 KB Output is correct
2 Correct 96 ms 16176 KB Output is correct
3 Correct 254 ms 16176 KB Output is correct
4 Correct 254 ms 16176 KB Output is correct
5 Correct 363 ms 16176 KB Output is correct
6 Correct 500 ms 16176 KB Output is correct
7 Correct 336 ms 16176 KB Output is correct
8 Correct 385 ms 16176 KB Output is correct
9 Execution timed out 2056 ms 17712 KB Time limit exceeded
10 Correct 905 ms 17712 KB Output is correct
11 Correct 1312 ms 17712 KB Output is correct
12 Execution timed out 2073 ms 17712 KB Time limit exceeded
13 Execution timed out 2068 ms 19080 KB Time limit exceeded