Submission #1212932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212932		stefanneagu	Cake (CEOI14_cake)	C++20	0 / 100	2096 ms	20372 KiB

cake

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 5e5 + 1, inf = 1e9;

int v[nmax];
int n;

struct aint_in_4h57min30sec {
    int aint[nmax * 4];
    int lz[nmax * 4];

   void init(int nod = 1, int st = 1, int dr = n) {
       for (int i = 1; i <= n; i++) {
           aint[i] = v[i];
       }
   }
/*
    void prop(int nod, int st, int dr) {
        if (lz[nod] == 0) {
            return;
        }
        aint[nod] += lz[nod];
        if (st != dr) {
            lz[nod * 2] += lz[nod];
            lz[nod * 2 + 1] += lz[nod];
        }
        lz[nod] = 0;
    }

    void hub(int nod, int st, int dr) {
        prop(nod, st, dr);
        if (st == dr) {
            return;
        }
        int mid = (st + dr) / 2;
        prop(nod * 2, st, mid);
        prop(nod * 2 + 1, mid + 1, dr);
    }*/

    void setval(int i, int val) {
       aint[i] = val;
   }

    void upd(int l, int r, int val) {
        for (int i = l; i <= r; i++) {
            aint[i] += val;
        }
    }

    int qry(int l, int r, int nod = 1, int st = 1, int dr = n) {
       int maxx = -inf;
       for (int i = l; i <= r; i++) {
           maxx = max(maxx, aint[i]);
       }
    }
} ds;

bool in[nmax];
pair<int, int> t10[12];

int geti(int val) {
    for (int i = 1; i <= 10; i++) {
        if (t10[i].second < val) {
            return i;
        }
    }
    assert(0);
}

void push_t10(int poz, int val, int ind) {
    pair<int, int> ult = {poz, val};
    in[poz] = 1;
    for (int i = ind; i <= 10; i++) {
        swap(t10[i], ult);
    }
    in[ult.first] = 0;
}

void erase_t10(int nr) {
    pair<int, int> ult = {0, 0};
    in[nr] = 0;
    for (int i = 10; i >= 1; i--) {
        swap(t10[i], ult);
        if (ult.first == nr) {
            return;
        }
    }
    assert(0);
}

int pos1;

int mare_dr(int val) {
    int l = pos1 + 1, r = n, ans = n + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ds.qry(pos1 + 1, mid) > val) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

int mare_st(int val) {
    int l = 1, r = pos1 - 1, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ds.qry(mid, pos1 - 1) > val) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void stanga(int i) {
    int vi = ds.qry(i, i);
    if (i == pos1 - 1) {
        int dr = mare_dr(vi);
        cout << dr - pos1 << '\n';
        return;
    }
    int mval = ds.qry(i + 1, pos1 - 1);
    int dr_mx1 = mare_dr(mval);
    if (dr_mx1 == n + 1 || ds.qry(dr_mx1, dr_mx1) > vi) {
        cout << dr_mx1 - i - 1 << '\n';
        return;
    } else {
        int max_dr = mare_dr(vi);
        cout << max_dr - i - 1 << '\n';
        return;
    }
}

void dreapta(int i) {
    int vi = ds.qry(i, i);
    if (i == pos1 + 1) {
        int st = mare_st(vi);
        cout << pos1 - st << '\n';
        return;
    }
    int mval = ds.qry(pos1 + 1, i - 1);
    int st_mx1 = mare_st(mval);
    if (st_mx1 == 0 || ds.qry(st_mx1, st_mx1) > vi) {
        cout << i - 1 - st_mx1 << '\n';
        return;
    } else {
        int max_st = mare_st(vi);
        cout << i - 1 - max_st << '\n';
        return;
    }
}

void norm() {
    map<int, int> N;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        N[v[i]];
    }
    for (auto &it : N) {
        it.second = ++cnt;
    }
    for (int i = 1; i <= n; i++) {
        v[i] = N[v[i]] + inf;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> pos1;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    v[pos1] = 0;
    norm();
    for (int i = 1; i <= n; i++) {
        if (i == pos1) {
            continue;
        }
        if (t10[10].second < v[i]) {
            push_t10(i, v[i], geti(v[i]));
        }
    }
    v[pos1] = 0;
    ds.init();
    int q;
    cin >> q;
    while (q--) {
        char t;
        cin >> t;
        if (t == 'E') {
            int i, poz;
            cin >> i >> poz;
            if (i == pos1) {
                continue;
            }
            if (in[i]) {
                erase_t10(i);
            }
            push_t10(i, t10[poz].second, poz);
            for (int j = poz + 1; j <= 10; j++) {
                t10[j].second--;
            }
            ds.upd(1, n, -1);
            for (int j = 1; j <= poz; j++) {
                ds.setval(t10[j].first, t10[j].second);
            }
        } else {
            int poz;
            cin >> poz;
            if (poz == pos1) {
                cout << "0\n";
                continue;
            }
            if (poz < pos1) {
                stanga(poz);
            } else {
                dreapta(poz);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In member function 'long long int aint_in_4h57min30sec::qry(long long int, long long int, long long int, long long int, long long int)':
cake.cpp:58:5: warning: no return statement in function returning non-void [-Wreturn-type]
   58 |     }
      |     ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50