Submission #164554

#	Time	Username	Problem	Language	Result	Execution time	Memory
164554		mhy908	Cake (CEOI14_cake)	C++14	0 / 100	533 ms	39172 KiB

cake

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
struct SEGMENT_TREE
{
    LL initial=-llinf;
    int x=-1;
    struct NODE{
        int st, fin;
        LL q;
    }tree[1000000];
    LL f(LL a, LL b){return max(a, b);}
    void init(int point, int num){
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        init(point*2, num-num/2);
        init(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void update(int point, int num, LL qu){
        if(tree[point].st==tree[point].fin){
            tree[point].q=qu;
            return;
        }
        if(num<=tree[point*2].fin)update(point*2, num, qu);
        else update(point*2+1, num, qu);
        tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
    }
    LL max_query(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].q;
        if(tree[point].st>b||tree[point].fin<a)return initial;
        return f(max_query(point*2, a, b), max_query(point*2+1, a, b));
    }
    int find_query1(int point, int a, int b, LL num){
        if(tree[point].st==tree[point].fin)return tree[point].st;
        if(tree[point*2].fin<a)return find_query1(point*2+1, a, b, num);
        if(tree[point*2+1].st>b)return find_query1(point*2, a, b, num);
        if(max_query(point*2, a, tree[point*2].fin)>=num)return find_query1(point*2, a, b, num);
        return find_query1(point*2+1, a, b, num);
    }
    int find_query2(int point, int a, int b, LL num){
        if(tree[point].st==tree[point].fin)return tree[point].st;
        if(tree[point*2].fin<a)return find_query2(point*2+1, a, b, num);
        if(tree[point*2+1].st>b)return find_query2(point*2, a, b, num);
        if(max_query(point*2+1, tree[point*2+1].st, b)>=num)return find_query2(point*2+1, a, b, num);
        return find_query2(point*2, a, b, num);
    }
    void init(int num){init(1, num);}
    void update(int num, LL qu){update(1, num, qu);}
    LL max_query(int a, int b){return max_query(1, a, b);}
    int find_query1(int a, int b, LL num){return find_query1(1, a, b, num);}
    int find_query2(int a, int b, LL num){return find_query2(1, a, b, num);}
}seg;
list<int> li;
int n, q, s, re1, re2;
LL d[250010];
pair<LL, int> temp[250010];
pair<pii, int> qu1[500010];
pair<int, int> qu2[500010];
LL t=300000;
LL change[500010];
int main()
{
    scanf("%d %d", &n, &s);
    seg.init(n+2);
    for(int i=1; i<=n; i++){
        scanf("%lld", &d[i]);
        temp[i]=mp(d[i], i);
    }
    scanf("%d", &q);
    for(int u=1; u<=q; u++){
        char c;
        scanf(" %c", &c);
        if(c=='F'){
            re2++;
            scanf("%d", &qu2[re2].F);
            qu2[re2].S=u;
        }
        else{
            re1++;
            scanf("%d %d", &qu1[re1].F.F, &qu1[re1].F.S);
            qu1[re1].S=u;
        }
    }
    sort(temp+1, temp+n+1);
    for(int i=max(1, n-9); i<=n; i++){
        li.pb(-temp[i].S);
    }
    for(int i=1; i<=re1; i++){
        auto it=li.end();
        for(int j=1; j<qu1[i].F.S; j++)it--;
        li.insert(it, qu1[i].S);
    }
    for(auto it=li.begin(); it!=li.end(); it++){
        int num=*it;
        if(num<0)d[-num]=++t;
        else change[num]=++t;
    }
    seg.update(0, llinf);
    seg.update(n+1, llinf);
    for(int i=1; i<=n; i++){
        if(i==s)continue;
        seg.update(i, d[i]);
    }
    int pv1=1, pv2=1;
    for(int i=1; i<=q; i++){
        if(i==qu1[pv1].S){
            if(qu1[pv1].F.F==s){
                pv1++;
                continue;
            }
            d[qu1[pv1].F.F]=change[i];
            seg.update(qu1[pv1].F.F, change[i]);
            pv1++;
        }
        else{
            if(qu2[pv2].F==s){
                puts("0");
                pv2++;
                continue;
            }
            if(s>qu2[pv2].F){
                LL tmp=seg.max_query(qu2[pv2].F, s);
                int ans=seg.find_query1(s, n+1, tmp);
                printf("%d\n", ans-qu2[pv2].F-1);
            }
            else{
                LL tmp=seg.max_query(s, qu2[pv2].F);
                int ans=seg.find_query2(0, s, tmp);
                printf("%d\n", qu2[pv2].F-ans-1);
            }
            pv2++;
        }
    }
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &s);
     ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &d[i]);
         ~~~~~^~~~~~~~~~~~~~~
cake.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
cake.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
cake.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &qu2[re2].F);
             ~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &qu1[re1].F.F, &qu1[re1].F.S);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50