oj.uz

Submission #941575

# Submission time Handle Problem Language Result Execution time Memory
941575 2024-03-09T07:30:21 Z quanlt206 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 1622 ms 24252 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 150007;
const int M = 407;
int n, L, a[N], Q, x[N], pos[N];

int S, numBlock = 0;

struct BLOCK {
    pii b[2 * M];
    pii f[2 * M];
    int sz;
    BLOCK() {
        REP(i, 0, 2 * M) b[i] = {0, 0};
        sz = 0;
    }
} block[M];

void print_block() {
    REP(i, 0, numBlock) {
        cout<<"block "<<i<<":\n";
        REP(j, 0, block[i].sz) cout<<block[i].b[j].X<<" "<<block[i].b[j].Y<<"\n";
        cout<<"array F : \n";
        REP(j, 0, block[i].sz) cout<<block[i].f[j].X<<" "<<block[i].f[j].Y<<"\n";
        cout<<"\n";
    }
}


void print_block(BLOCK& a) {
    cout<<"array b : \n";
    REP(j, 0, a.sz) cout<<a.b[j].X<<" "<<a.b[j].Y<<"\n";
    cout<<"array F : \n";
    REP(j, 0, a.sz) cout<<a.f[j].X<<" "<<a.f[j].Y<<"\n";
    cout<<"\n";
}

void init_block_data(BLOCK& a) {
    int j = a.sz - 1;
    FORD(i, a.sz - 1, 0) {
        while (j > i && a.b[i].X + L < a.b[j].X) j--;
        if (j == a.sz - 1) a.f[i] = {1, a.b[i].X + L}; else a.f[i] = {a.f[j + 1].X + 1, a.f[j + 1].Y};
    }
}

void init(int nn, int LL, int x[]) {
    n = nn;
    L = LL;
    REP(i, 0, n) a[i] = x[i];
    S = sqrt(n);
    for (int i = 0; i < n; i+=S) {
        FOR(j, i, min(n - 1, i + S - 1)) {
            block[numBlock].b[block[numBlock].sz++] = {a[j], j};
            pos[j] = numBlock;
        }
        init_block_data(block[numBlock]);
        numBlock++;
    }
//    print_block();
}

pii c[N];

void rebuild_block() {
    int m = 0;
    REP(i, 0, numBlock)
        REP(j, 0, block[i].sz) c[m++] = block[i].b[j];
    numBlock = 0;
    for (int i = 0; i < n; i+=S) {
        block[numBlock].sz = 0;
        FOR(j, i, min(n - 1, i + S - 1)) {
            block[numBlock].b[block[numBlock].sz++] = c[j];
            pos[c[j].Y] = numBlock;
        }
        init_block_data(block[numBlock]);
        numBlock++;
    }
}

void delete_element_in_block(BLOCK& a, int pos) {
    // x la vi tri
    REP(i, 0, a.sz)
        if (a.b[i].Y == pos) {
//            print_block(a);
            REP(j, i, a.sz - 1) a.b[j] = a.b[j + 1];
            a.sz--;
//            print_block(a);
            break;
        }
    init_block_data(a);
}

void add_element(BLOCK& a, int pos, int val) {
    if (a.sz == 0) {
        a.b[a.sz++] = {val, pos};
    }
    else
    if (val <= a.b[0].X) {
        FORD(j, a.sz, 1) a.b[j] = a.b[j - 1];
        a.b[0] = {val, pos};
        a.sz++;
    }
    else
    if (val >= a.b[a.sz - 1].X) {
        a.b[a.sz] = {val, pos};
        a.sz++;
    }
    else {
        REP(i, 1, a.sz)
            if (val <= a.b[i].X) {
                FORD(j, a.sz, i + 1) a.b[j] = a.b[j - 1];
                a.b[i] = {val, pos};
                a.sz++;
                break;
            }
    }
//    print_block(a);
    init_block_data(a);
}

void add_element(int POS, int val) {
    REP(i, 0, numBlock)
        if (val <= block[i].b[block[i].sz - 1].X || i == numBlock - 1) {
            pos[POS] = i;
            add_element(block[i], POS, val);
            break;
        }
    REP(i, 0, numBlock)
        if (block[i].sz > 2 * S) {
            rebuild_block();
            break;
        }
}

void update_block(int i, int y) {
    delete_element_in_block(block[pos[i]], i);
//    exit(0);
//    exit(0);
    a[i] = y;
    add_element(i, a[i]);
//    print_block();
}

int get_answer() {
    int pos_not_empty = 0;
    REP(i, 0, numBlock)
        if (block[i].sz > 0) {
            pos_not_empty = i;
            break;
        }
    int res = block[pos_not_empty].f[0].X, tmp = block[pos_not_empty].f[0].Y;
    REP(i, pos_not_empty + 1, numBlock) {
        if (tmp >= block[i].b[block[i].sz - 1].X) continue;
        int d = 0, c = (int)block[i].sz - 1, g, ans = -1;
        while (d <= c) {
            g = (d + c) >> 1;
            if (tmp >= block[i].b[g].X) ans = g, d = g + 1; else c = g - 1;
        }
        ans++;
        res+=block[i].f[ans].X;
        tmp = block[i].f[ans].Y;
    }
    return res;
}

int update(int i, int y) {
    update_block(i, y);
    return get_answer();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 133 ms 15644 KB Output is correct
8 Correct 160 ms 15684 KB Output is correct
9 Correct 258 ms 16336 KB Output is correct
10 Correct 239 ms 16208 KB Output is correct
11 Correct 185 ms 16220 KB Output is correct
12 Correct 318 ms 16384 KB Output is correct
13 Correct 253 ms 16084 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 133 ms 15644 KB Output is correct
8 Correct 160 ms 15684 KB Output is correct
9 Correct 258 ms 16336 KB Output is correct
10 Correct 239 ms 16208 KB Output is correct
11 Correct 185 ms 16220 KB Output is correct
12 Correct 318 ms 16384 KB Output is correct
13 Correct 253 ms 16084 KB Output is correct
14 Correct 153 ms 18236 KB Output is correct
15 Correct 244 ms 18240 KB Output is correct
16 Correct 427 ms 18644 KB Output is correct
17 Correct 510 ms 18860 KB Output is correct
18 Correct 547 ms 18968 KB Output is correct
19 Correct 426 ms 19024 KB Output is correct
20 Correct 521 ms 19036 KB Output is correct
21 Correct 494 ms 19000 KB Output is correct
22 Correct 411 ms 18524 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 133 ms 15644 KB Output is correct
8 Correct 160 ms 15684 KB Output is correct
9 Correct 258 ms 16336 KB Output is correct
10 Correct 239 ms 16208 KB Output is correct
11 Correct 185 ms 16220 KB Output is correct
12 Correct 318 ms 16384 KB Output is correct
13 Correct 253 ms 16084 KB Output is correct
14 Correct 153 ms 18236 KB Output is correct
15 Correct 244 ms 18240 KB Output is correct
16 Correct 427 ms 18644 KB Output is correct
17 Correct 510 ms 18860 KB Output is correct
18 Correct 547 ms 18968 KB Output is correct
19 Correct 426 ms 19024 KB Output is correct
20 Correct 521 ms 19036 KB Output is correct
21 Correct 494 ms 19000 KB Output is correct
22 Correct 411 ms 18524 KB Output is correct
23 Correct 1317 ms 23900 KB Output is correct
24 Correct 1390 ms 23900 KB Output is correct
25 Correct 1204 ms 24108 KB Output is correct
26 Correct 1456 ms 24076 KB Output is correct
27 Correct 1610 ms 23932 KB Output is correct
28 Correct 270 ms 22060 KB Output is correct
29 Correct 241 ms 21816 KB Output is correct
30 Correct 263 ms 21852 KB Output is correct
31 Correct 244 ms 22100 KB Output is correct
32 Correct 1096 ms 23636 KB Output is correct
33 Correct 981 ms 22976 KB Output is correct
34 Correct 1275 ms 23720 KB Output is correct
35 Correct 1054 ms 24252 KB Output is correct
36 Correct 724 ms 23340 KB Output is correct
37 Correct 1254 ms 23908 KB Output is correct
38 Correct 1342 ms 22716 KB Output is correct
39 Correct 1337 ms 23752 KB Output is correct
40 Correct 1312 ms 22868 KB Output is correct
41 Correct 1616 ms 23500 KB Output is correct
42 Correct 1622 ms 23736 KB Output is correct