oj.uz

답안 #164559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
164559 2019-11-21T13:10:13 Z mhy908 케이크 (CEOI14_cake) C++14
0 / 100
 561 ms 41308 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;
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=1; 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 504 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 233 ms 27020 KB Output isn't correct
2 Correct 203 ms 26976 KB Output is correct
3 Correct 216 ms 26992 KB Output is correct
4 Correct 191 ms 27000 KB Output is correct
5 Incorrect 244 ms 28740 KB Output isn't correct
6 Correct 228 ms 28792 KB Output is correct
7 Correct 231 ms 28988 KB Output is correct
8 Correct 204 ms 28820 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 12280 KB Output is correct
2 Correct 146 ms 12088 KB Output is correct
3 Correct 107 ms 12152 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 253 ms 24604 KB Output is correct
6 Incorrect 205 ms 24668 KB Output isn't correct
7 Correct 188 ms 24388 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 2552 KB Output isn't correct
2 Correct 35 ms 2940 KB Output is correct
3 Correct 81 ms 8540 KB Output is correct
4 Correct 75 ms 8444 KB Output is correct
5 Incorrect 83 ms 6520 KB Output isn't correct
6 Correct 148 ms 12192 KB Output is correct
7 Correct 126 ms 9336 KB Output is correct
8 Correct 144 ms 20728 KB Output is correct
9 Incorrect 561 ms 41256 KB Output isn't correct
10 Incorrect 274 ms 18964 KB Output isn't correct
11 Correct 335 ms 21240 KB Output is correct
12 Correct 526 ms 38408 KB Output is correct
13 Incorrect 487 ms 41308 KB Output isn't correct