oj.uz

답안 #164561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
164561 2019-11-21T13:40:24 Z mhy908 케이크 (CEOI14_cake) C++14
100 / 100
 1792 ms 28028 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;
set<pair<LL, int> > se;
int n, q, s, re1, re2;
LL d[250010];

int main()
{
    scanf("%d %d", &n, &s);
    seg.init(n+2);
    for(int i=1; i<=n; i++){
        scanf("%lld", &d[i]);
        se.insert(mp(d[i], i));
        if(i==s)continue;
        seg.update(i, d[i]);
    }
    scanf("%d", &q);
    seg.update(0, llinf);
    seg.update(n+1, llinf);
    for(int u=1; u<=q; u++){
        char c;
        scanf(" %c", &c);
        if(c=='F'){
            int temp;
            scanf("%d", &temp);
            if(temp==s){
                puts("0");
                continue;
            }
            if(s>temp){
                LL tmp=seg.max_query(temp, s-1);
                int ans=seg.find_query1(s+1, n+1, tmp);
                printf("%d\n", ans-temp-1);
            }
            else{
                LL tmp=seg.max_query(s+1, temp);
                int ans=seg.find_query2(0, s-1, tmp);
                printf("%d\n", temp-ans-1);
            }
        }
        else{
            int a, b;
            scanf("%d %d", &a, &b);
            auto it=se.find(mp(d[a], a)), it2=se.end();
            it2--;
            se.erase(it);
            vector<int> p;
            for(int i=1; i<=b; i++){
                if(i==b){
                    d[a]=it2->F+1;
                    se.insert(mp(d[a], a));
                    seg.update(a, d[a]);
                }
                else{
                    p.pb(it2->S);
                }
                it2--;
            }
            for(int i=0; i<b-1; i++){
                se.erase(mp(d[p[i]], p[i]));
                d[p[i]]++;
                se.insert(mp(d[p[i]], p[i]));
                seg.update(p[i], d[p[i]]);
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:69: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:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &d[i]);
         ~~~~~^~~~~~~~~~~~~~~
cake.cpp:77: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", &temp);
             ~~~~~^~~~~~~~~~~~~
cake.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 504 KB Output is correct
5 Correct 27 ms 1784 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 788 ms 1528 KB Output is correct
2 Correct 404 ms 1628 KB Output is correct
3 Correct 564 ms 1656 KB Output is correct
4 Correct 293 ms 1656 KB Output is correct
5 Correct 893 ms 3192 KB Output is correct
6 Correct 738 ms 3320 KB Output is correct
7 Correct 717 ms 3200 KB Output is correct
8 Correct 355 ms 3192 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 12024 KB Output is correct
2 Correct 157 ms 11896 KB Output is correct
3 Correct 139 ms 11896 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 396 ms 26872 KB Output is correct
6 Correct 394 ms 26904 KB Output is correct
7 Correct 242 ms 26616 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 888 KB Output is correct
2 Correct 67 ms 1064 KB Output is correct
3 Correct 159 ms 6096 KB Output is correct
4 Correct 211 ms 6292 KB Output is correct
5 Correct 229 ms 964 KB Output is correct
6 Correct 295 ms 7496 KB Output is correct
7 Correct 236 ms 2040 KB Output is correct
8 Correct 381 ms 11612 KB Output is correct
9 Correct 1792 ms 27896 KB Output is correct
10 Correct 752 ms 1784 KB Output is correct
11 Correct 1058 ms 4320 KB Output is correct
12 Correct 1772 ms 24500 KB Output is correct
13 Correct 1313 ms 28028 KB Output is correct