oj.uz

답안 #176072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
176072 2020-01-07T20:12:12 Z stefdasca 케이크 (CEOI14_cake) C++14
100 / 100
 694 ms 12352 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, a, v[250002], whr[250002];

int q;

int aint[1000002], poz[1000002];

vector<pair<int, int> >top;

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = v[st];
        poz[nod] = st;
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    if(st >= a)
    {
        if(aint[nod << 1] >= aint[nod << 1|1])
            aint[nod] = aint[nod << 1], poz[nod] = poz[nod << 1];
        else
            aint[nod] = aint[nod << 1|1], poz[nod] = poz[nod << 1|1];
    }
    else
        if(aint[nod << 1] > aint[nod << 1|1])
            aint[nod] = aint[nod << 1], poz[nod] = poz[nod << 1];
        else
            aint[nod] = aint[nod << 1|1], poz[nod] = poz[nod << 1|1];
}

void upd(int nod, int st, int dr, int pz, int val)
{
    if(st == dr)
    {
        aint[nod] = val;
        poz[nod] = st;
        return;
    }
    int mid = (st + dr) / 2;
    if(pz <= mid)
        upd(nod << 1, st, mid, pz, val);
    else
        upd(nod << 1|1, mid+1, dr, pz, val);
    if(st >= a)
    {
        if(aint[nod << 1] >= aint[nod << 1|1])
            aint[nod] = aint[nod << 1], poz[nod] = poz[nod << 1];
        else
            aint[nod] = aint[nod << 1|1], poz[nod] = poz[nod << 1|1];
    }
    else
        if(aint[nod << 1] > aint[nod << 1|1])
            aint[nod] = aint[nod << 1], poz[nod] = poz[nod << 1];
        else
            aint[nod] = aint[nod << 1|1], poz[nod] = poz[nod << 1|1];
}

int qumx(int nod, int st, int dr, int L, int R)
{
    if(dr < L || st > R)
        return 0;
    if(L <= st && dr <= R)
        return aint[nod];
    int mid = (st + dr) / 2;
    return max(qumx(nod << 1, st, mid, L, R), qumx(nod << 1|1, mid+1, dr, L, R));
}
int mxval;
int query1(int nod, int st, int dr, int L, int R)
{
    if(dr < L || st > R)
        return -1;
    if(aint[nod] < mxval)
        return -1;
    if(st == dr)
        return poz[nod];
    int mid = (st + dr) / 2;
    int ans = query1(nod << 1|1, mid+1, dr, L, R);
    if(ans != -1)
        return ans;
    return query1(nod << 1, st, mid, L, R);
}

int query2(int nod, int st, int dr, int L, int R)
{
    if(dr < L || st > R)
        return -1;
    if(aint[nod] < mxval)
        return -1;
    if(st == dr)
        return poz[nod];
    int mid = (st + dr) / 2;
    int ans = query2(nod << 1, st, mid, L, R);
    if(ans != -1)
        return ans;
    return query2(nod << 1|1, mid+1, dr, L, R);
}
map<int, int> wazz;
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> a;
    for(int i = 1; i <= n; ++i)
        cin >> v[i], whr[v[i]] = i;
    for(int i = 1; i <= n; ++i)
        top.pb({i, whr[i]});
    build(1, 1, n);
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        char tip;
        cin >> tip;
        if(tip == 'E')
        {
            int poz, plz;
            cin >> poz >> plz;
            deque<pair<int, int> >vals;
            wazz.clear();
            wazz[poz] = 1;
            while(vals.size() + 1 < plz)
            {
                if(wazz.find(top.back().se) != wazz.end())
                    top.pop_back();
                else
                    wazz[top.back().se] = 1, vals.push_front(top.back()), top.pop_back();
            }
            upd(1, 1, n, poz, top.back().fi + 1);
            top.pb({top.back().fi + 1, poz});
            while(!vals.empty())
            {
                upd(1, 1, n, vals.front().se, top.back().fi + 1);
                top.pb({top.back().fi + 1, vals.front().se});
                vals.pop_front();
            }
        }
        else
        {
            int poz;
            cin >> poz;
            if(poz == a)
                cout << 0 << '\n';
            else
            {
                if(a == 1 || a == n)
                    cout << abs(poz - a) << '\n';
                else
                    if(poz > a)
                    {
                        int ans = poz - a;
                        mxval = qumx(1, 1, n, a + 1, poz);
                        int p2 = query1(1, 1, n, 1, a - 1);
                        if(p2 == -1)
                            p2 = 0;
                        ans += a - 1 - p2;
                        cout << ans << '\n';
                    }
                    else
                    {
                        int ans = a - poz;
                        mxval = qumx(1, 1, n, poz, a - 1);
                        int p2 = query2(1, 1, n, a + 1, n);
                        if(p2 == -1)
                            p2 = n + 1;
                        ans += p2 - a - 1;
                        cout << ans << '\n';
                    }
            }
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:147:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(vals.size() + 1 < plz)
                   ~~~~~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 14 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 506 ms 2992 KB Output is correct
2 Correct 325 ms 4968 KB Output is correct
3 Correct 358 ms 4968 KB Output is correct
4 Correct 221 ms 4972 KB Output is correct
5 Correct 534 ms 5404 KB Output is correct
6 Correct 461 ms 3328 KB Output is correct
7 Correct 383 ms 9588 KB Output is correct
8 Correct 237 ms 9460 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 4680 KB Output is correct
2 Correct 70 ms 4592 KB Output is correct
3 Correct 59 ms 4588 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 106 ms 9248 KB Output is correct
6 Correct 106 ms 9196 KB Output is correct
7 Correct 86 ms 8952 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 888 KB Output is correct
2 Correct 39 ms 1016 KB Output is correct
3 Correct 73 ms 3060 KB Output is correct
4 Correct 94 ms 3060 KB Output is correct
5 Correct 148 ms 2016 KB Output is correct
6 Correct 135 ms 4540 KB Output is correct
7 Correct 144 ms 2164 KB Output is correct
8 Correct 183 ms 7564 KB Output is correct
9 Correct 694 ms 12352 KB Output is correct
10 Correct 487 ms 3664 KB Output is correct
11 Correct 552 ms 6688 KB Output is correct
12 Correct 689 ms 11472 KB Output is correct
13 Correct 559 ms 11920 KB Output is correct