oj.uz

답안 #164554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
164554 2019-11-21T12:28:24 Z mhy908 케이크 (CEOI14_cake) C++14
0 / 100
 533 ms 39172 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 31004 KB Output isn't correct
2 Correct 206 ms 31032 KB Output is correct
3 Correct 235 ms 30980 KB Output is correct
4 Correct 190 ms 31104 KB Output is correct
5 Incorrect 239 ms 32164 KB Output isn't correct
6 Correct 225 ms 32376 KB Output is correct
7 Correct 226 ms 32276 KB Output is correct
8 Correct 203 ms 32580 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 9988 KB Output is correct
2 Correct 109 ms 9732 KB Output is correct
3 Correct 116 ms 9704 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 186 ms 18684 KB Output is correct
6 Incorrect 182 ms 18680 KB Output isn't correct
7 Correct 172 ms 18424 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 2680 KB Output isn't correct
2 Correct 35 ms 2868 KB Output is correct
3 Correct 77 ms 7252 KB Output is correct
4 Correct 74 ms 7188 KB Output is correct
5 Incorrect 85 ms 6904 KB Output isn't correct
6 Correct 143 ms 11100 KB Output is correct
7 Correct 127 ms 9848 KB Output is correct
8 Correct 137 ms 19704 KB Output is correct
9 Incorrect 533 ms 39168 KB Output isn't correct
10 Incorrect 280 ms 21880 KB Output isn't correct
11 Correct 333 ms 24236 KB Output is correct
12 Correct 496 ms 37496 KB Output is correct
13 Incorrect 459 ms 39172 KB Output isn't correct