Submission #1246725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246725		mosesmayer	Infinite Race (EGOI24_infiniterace2)	C++20	22 / 100	3 ms	1096 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

template<class T> inline T re(){
    T N = 0; char c = getchar(); bool neg = 0;
    for (; c < '0' || c > '9'; c = getchar()) neg |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        N = (N<<3)+(N<<1) + c - '0';
    return neg ? -N : N;
}

const int MX = 2e5;
int n, q;
int qs[MX];
// unordered_set<int> in_front, behind, tmp;
int tot = 0;

int in_front[MX * 4 + 5], behind[MX * 4 + 5];
int lz_front[MX * 4 + 5], lz_behind[MX * 4 + 5];
void build(int* st, int* lz, int p = 1, int l = 0, int r = n - 1) {
    if (l == r) {
        st[p] = 0, lz[p] = -1;
    } else {
        int md = (l + r) >> 1;
        build(st, lz, p << 1, l, md);
        build(st, lz, p << 1 | 1, md + 1, r);
        st[p] = 0, lz[p] = -1;
    }
}
void prop(int* st, int* lz, int p, int l, int r) { // set values
    if (lz[p] == -1) return;
    st[p] = lz[p];
    if (l < r) {
        lz[p << 1] = lz[p];
        lz[p << 1 | 1] = lz[p];
    }
    lz[p] = -1;
}

void upd_set(int i, int j, int x, int* st, int* lz, int p = 1, int l = 0, int r = n - 1){ 
    prop(st, lz, p, l, r);
    if (j < l || i > r) return;
    if (i <= l && j >= r) {
        lz[p] = x;
        prop(st, lz, p, l, r);
    } else {
        int md = (l + r) >> 1;
        upd_set(i, j, x, st, lz, p << 1, l, md);
        upd_set(i, j, x, st, lz, p << 1 | 1, md + 1, r);
        st[p] = x;
    }
}

int get(int pos, int* st, int* lz, int p = 1, int l = 0, int r = n - 1) {
    prop(st, lz, p, l, r);
    if (l == r) {
        return st[p];
    }
    int md = (l + r) >> 1;
    if (pos <= md) return get(pos, st, lz, p << 1, l, md);
    else return get(pos, st, lz, p << 1 | 1, md + 1, r);
}

int main() {
    n = re<int>(); q = re<int>();
    for (int i = 1; i <= q; i++) qs[i] = re<int>();
    build(in_front, lz_front);
    build(behind, lz_behind);
    upd_set(1, n - 1, 1, in_front, lz_front);
    // for (int i = 1; i < n; i++) {
        //in_front.insert(i);
    // }
    for (int i = 1; i <= q; i++) {
        //cerr << "QS :: " << qs[i] << '\n';
        if (qs[i] > 0) {
            if (get(qs[i], in_front, lz_front) == 1) {
                //cerr << "Case 1\n";
                /* same lap */
                upd_set(qs[i], qs[i], 0, in_front, lz_front);
                upd_set(qs[i], qs[i], 1, behind, lz_behind);
            } else {
                //cerr << "Case 2\n";
                /* already behind - overtake
                 * move all behind to in front
                 */
                upd_set(1, n - 1, 0, behind, lz_behind);
                upd_set(qs[i], qs[i], 1, behind, lz_behind);
                upd_set(1, n - 1, 1, in_front, lz_front);
                upd_set(qs[i], qs[i], 0, in_front, lz_front);
                tot++;
            }
            //if (in_front.find(qs[i]) != in_front.end()) {
            //    /* same lap */
            //    // in_front.erase(in_front.find(qs[i]));
            //    // behind.insert(qs[i]);
            //} else {
            //}
        } else {
            if (get(-qs[i], behind, lz_behind) == 1) {
                //cerr << "Case 3\n";
                upd_set(-qs[i], -qs[i], 0, behind, lz_behind);
                upd_set(-qs[i], -qs[i], 1, in_front, lz_front);
            } else {
                //cerr << "Case 4\n";
            }
            //if (behind.find(qs[i]) != behind.end()) {
            //    /* same lap */
            //    // behind.erase(behind.find(qs[i]));
            //    // in_front.insert(qs[i]);
            //} else {
            //    /* get lapped - do nothing */
            //}
        }
        //cerr<< "front: "; for (int j = 1; j < n; j++) //cerr << get(j, in_front, lz_front) << " \n"[j + 1 == n];
        //cerr << "back: "; for (int j = 1; j < n; j++) //cerr << get(j, behind, lz_behind) << " \n"[j + 1 == n];
        //cerr << "tot: " << tot << '\n';
    }
    printf("%d\n", tot);
    return 0;
}

• Subtask 1: 0 / 29
• Subtask 2: 0 / 34
• Subtask 3: 22 / 22
• Subtask 4: 0 / 15