oj.uz

답안 #176066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
176066 2020-01-07T19:44:32 Z stefdasca 케이크 (CEOI14_cake) C++14
0 / 100
 575 ms 16744 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(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(L <= st && dr <= R)
        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(L <= st && dr <= R)
        return poz[nod];
    int mid = (st + dr) / 2;
    int ans = query1(nod << 1, st, mid, L, R);
    if(ans != -1)
        return ans;
    return query1(nod << 1|1, mid+1, dr, L, R);
}
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 = max(1, n - 9); 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;
            while(vals.size() + 1 < plz)
                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:136:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(vals.size() + 1 < plz)
                   ~~~~~~~~~~~~~~~~^~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 401 ms 9200 KB Output isn't correct
2 Correct 301 ms 9168 KB Output is correct
3 Incorrect 328 ms 9184 KB Output isn't correct
4 Correct 231 ms 9332 KB Output is correct
5 Incorrect 434 ms 9880 KB Output isn't correct
6 Incorrect 367 ms 10236 KB Output isn't correct
7 Incorrect 350 ms 9952 KB Output isn't correct
8 Correct 235 ms 10168 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 5184 KB Output isn't correct
2 Incorrect 63 ms 5088 KB Output isn't correct
3 Incorrect 58 ms 4940 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 103 ms 9504 KB Output isn't correct
6 Incorrect 102 ms 9592 KB Output isn't correct
7 Correct 84 ms 9336 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 1272 KB Output isn't correct
2 Incorrect 36 ms 1400 KB Output isn't correct
3 Incorrect 66 ms 3544 KB Output isn't correct
4 Incorrect 77 ms 3576 KB Output isn't correct
5 Incorrect 115 ms 3036 KB Output isn't correct
6 Incorrect 125 ms 5112 KB Output isn't correct
7 Incorrect 134 ms 3820 KB Output isn't correct
8 Incorrect 165 ms 7500 KB Output isn't correct
9 Incorrect 575 ms 16744 KB Output isn't correct
10 Incorrect 373 ms 7460 KB Output isn't correct
11 Incorrect 442 ms 8772 KB Output isn't correct
12 Incorrect 557 ms 15732 KB Output isn't correct
13 Incorrect 462 ms 16616 KB Output isn't correct