Submission #1200076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200076		abbvsss	September (APIO24_september)	C++20	0 / 100	1 ms	320 KiB

september

#include <bits/stdc++.h>

using namespace std;

vector<int> tree;
vector<int> lazy;

void build(int v, int l, int r, int x){
    if (l == r){
        tree[v] = x;
        return;
    }
    int m = (l + r) / 2;

    build(2 * v + 1, l, m, x);
    build(2 * v + 2, m + 1, r, x);

    tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}

void push(int v) {
    tree[2 * v + 1] = lazy[v];
    lazy[2 * v + 1] = lazy[v];
    tree[2 * v + 2] = lazy[v];
    lazy[2 * v + 2] = lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        tree[v] = addend;
        lazy[v] = addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(2 * v + 1, tl, tm, l, min(r, tm), addend);
        update(2 * v + 2, tm+1, tr, max(l, tm+1), r, addend);
        tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }
}

int get(int v, int l, int r, int i){
    if (l == r) {
        return tree[v];
    } 
    int m = (l + r) / 2;
    if (i <= m) return get(2 * v + 1, l, m, i);
    return get(2 * v + 2, m + 1, r, i);
}

int solve(int n, int m, vector<int> F, vector<vector<int>> S){

    tree.resize(4 * n);
    lazy.resize(4 * n);

    build(0, 0, n - 1, -1);

    vector<vector<int>> idxs(n, vector<int> (m));

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j ++){
            idxs[S[j][i]][j] = i;
        }
    }

    int k = 0;

    for (int i = 0; i < n; i++){
        if (get(0, 0, n - 1, i) != -1){
            int x = 0;
            for (int j = 0; j < m; j++){
                x = max(x, idxs[S[0][i]][j]);
            }
            update(0, 0, n - 1, i, x, k);
        }else{
            int x = 0;
            for (int j = 0; j < m; j++){
                x = max(x, idxs[S[0][i]][j]);
            }
            update(0, 0, n - 1, i, x, ++k);
        }
    }

    return k;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16