oj.uz

Submission #1117752

# Submission time Handle Problem Language Result Execution time Memory
1117752 2024-11-24T08:02:51 Z Mike_Vu Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3414 ms 19844 KB 
#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 15e4+5, B = 1000; ///B = 1000
int n, sumqu = 0, numblock, len, curpos[maxn];
vector<int> a; ///all positions
vector<vector<int>> b, cost, nxt; ///blocks
vector<int> temp; //for some use :V

void precal(vector<int> &b, vector<int> &cost, vector<int> &nxt) {
    //init
    int sz = b.size();
    cost.assign(sz, 0);
    nxt.assign(sz, 0);
    int j = sz;
    for (int i = sz-1; i >= 0; i--) {
        while (j-1 > i && b[i]+len < b[j-1]) {
            --j;
        }
        //init case
        if (j == sz) {
            cost[i] = 1;
            nxt[i] = b[i] + len;
        }
        else {
            cost[i] = cost[j] + 1;
            nxt[i] = nxt[j];
        }
    }
//    cout << "block:\n";
//    for (int i = 0; i < sz; i++) {
//        cout << b[i] << ' ';
//    }
//    cout << "\n";
//    for (int i = 0; i < sz; i++) {
//        cout << cost[i] << ' ';
//    }
//    cout << "\n";
//    for (int i = 0; i < sz; i++) {
//        cout << nxt[i] << ' ';
//    }
//    cout << "\n";
}

void extract() {
    a.clear();
    for (int j = 0; j < numblock; j++) {
        for (int i = 0; i < (int)b[j].size(); i++) {
            a.pb(b[j][i]);
        }
    }
}

void buildblocks() {
    for (int i= 0; i < numblock; i++) {
        b[i].clear();
    }
    for (int i = 0; i < n; i++) {
        b[i/B].pb(a[i]);
    }
    //cal blocks
    for (int i = 0; i < numblock; i++) {
        precal(b[i], cost[i], nxt[i]);
    }
}

void remval(int pos) {
    int j = -1;
    for (int k = numblock >> 1; k; k >>= 1) {
        while (j+k < numblock-1 && b[j+k].back() < pos) j += k;
    }
    ++j;
    //this is the right block
    bool found = 0;
    for (int i = 0; i < (int)b[j].size(); i++) {
        if (found || b[j][i] != pos) {
            temp.pb(b[j][i]);
        }
        else {
            found = 1;
        }
    }
    swap(b[j], temp);
    temp.clear();
//    for (int i = 0; i < (int)b[j].size(); i++) {
//        cout << b[j][i] << ' ';
//    }
//    cout << endl;
    precal(b[j], cost[j], nxt[j]);
}

void insval(int pos) {
    int j = -1;
    for (int k = numblock >> 1; k; k >>= 1) {
        while (j+k < numblock-1 && b[j+k].back() < pos) j += k;
    }
    ++j;
//    cout << j << endl;
//    system("pause");
    //this is the right block
    bool found = 0;
    for (int i = 0; i < (int)b[j].size(); i++) {
        if (!found && pos < b[j][i]) {
            found = 1;
            temp.pb(pos);
        }
        temp.pb(b[j][i]);
    }
    if (!found) temp.pb(pos);
//    system("pause");
    swap(b[j], temp);
    temp.clear();
//    for (int i = 0; i < (int)b[j].size(); i++) {
//        cout << b[j][i] << ' ';
//    }
//    cout << endl;
//    system("pause");
    precal(b[j], cost[j], nxt[j]);
}

int getans() {
    int curnxt = -1, res = 0;
    for (int j = 0; j < numblock; j++) {
        //case nxt this block cover all of the next block
        if (curnxt >= b[j].back()) continue;
        //binsearch
        int sz = b[j].size(), i = sz-1;
        for (int k = sz>>1; k; k >>= 1){
            while (i-k >= 0 && b[j][i-k] > curnxt) i -= k;
        }
        curnxt = nxt[j][i];
        res += cost[j][i];
    }
    return res;
}

void init(int N, int L, int X[]) {
    //normal
    n = N;
    len = L;
    numblock = (n-1)/B+1;
    b.assign(numblock, vector<int>());
    cost.assign(numblock, vector<int>());
    nxt.assign(numblock, vector<int>());
    for (int i = 0; i < n; i++) {
        a.pb(X[i]);
        curpos[i] = a[i];
    }
    //build blocks
    buildblocks();
}

int update(int id, int pos) {
    //normal
    ++sumqu;
    //remove
    remval(curpos[id]);
//    system("pause");
    //insert
    insval(pos);
    curpos[id] = pos;
//    cout << "ok"  << endl;
//    system("pause");
    //answer -> binsearch
    int ans = getans();
//    system("pause");
    //rebuild:
    if (sumqu % (B-1) == 0) {
//        cout << "entering rebuild" << endl;
//        system("pause");
        extract();
//        system("pause");
        buildblocks();
    }
    return ans;
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int n, l;
    int x[maxn];
    cin >> n >> l;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    init(n, l, x);
    int q;
    cin >> q;
    while (q--) {
        int id, pos;
        cin >> id >> pos;
        cout << update(id, pos) << "\n";
    }
}
#endif // mikevui
/*
4 10
10 15 17 20
5
2 16
1 25
3 35
0 38
2 0
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 8528 KB Output is correct
3 Correct 1 ms 8696 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 506 ms 9808 KB Output is correct
8 Correct 516 ms 10056 KB Output is correct
9 Correct 580 ms 13228 KB Output is correct
10 Correct 662 ms 13040 KB Output is correct
11 Correct 597 ms 13004 KB Output is correct
12 Correct 872 ms 13416 KB Output is correct
13 Correct 588 ms 12748 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 8528 KB Output is correct
3 Correct 1 ms 8696 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 506 ms 9808 KB Output is correct
8 Correct 516 ms 10056 KB Output is correct
9 Correct 580 ms 13228 KB Output is correct
10 Correct 662 ms 13040 KB Output is correct
11 Correct 597 ms 13004 KB Output is correct
12 Correct 872 ms 13416 KB Output is correct
13 Correct 588 ms 12748 KB Output is correct
14 Correct 691 ms 10568 KB Output is correct
15 Correct 753 ms 10544 KB Output is correct
16 Correct 1589 ms 13604 KB Output is correct
17 Correct 1436 ms 14568 KB Output is correct
18 Correct 1584 ms 14424 KB Output is correct
19 Correct 858 ms 14004 KB Output is correct
20 Correct 1426 ms 14548 KB Output is correct
21 Correct 1343 ms 14528 KB Output is correct
22 Correct 871 ms 13488 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 8528 KB Output is correct
3 Correct 1 ms 8696 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 506 ms 9808 KB Output is correct
8 Correct 516 ms 10056 KB Output is correct
9 Correct 580 ms 13228 KB Output is correct
10 Correct 662 ms 13040 KB Output is correct
11 Correct 597 ms 13004 KB Output is correct
12 Correct 872 ms 13416 KB Output is correct
13 Correct 588 ms 12748 KB Output is correct
14 Correct 691 ms 10568 KB Output is correct
15 Correct 753 ms 10544 KB Output is correct
16 Correct 1589 ms 13604 KB Output is correct
17 Correct 1436 ms 14568 KB Output is correct
18 Correct 1584 ms 14424 KB Output is correct
19 Correct 858 ms 14004 KB Output is correct
20 Correct 1426 ms 14548 KB Output is correct
21 Correct 1343 ms 14528 KB Output is correct
22 Correct 871 ms 13488 KB Output is correct
23 Correct 2807 ms 18292 KB Output is correct
24 Correct 2856 ms 18292 KB Output is correct
25 Correct 2106 ms 18292 KB Output is correct
26 Correct 2413 ms 18344 KB Output is correct
27 Correct 2693 ms 10684 KB Output is correct
28 Correct 2150 ms 11796 KB Output is correct
29 Correct 2055 ms 11572 KB Output is correct
30 Correct 1972 ms 11704 KB Output is correct
31 Correct 1866 ms 11792 KB Output is correct
32 Correct 1937 ms 17768 KB Output is correct
33 Correct 1690 ms 17092 KB Output is correct
34 Correct 1913 ms 17972 KB Output is correct
35 Correct 1905 ms 19844 KB Output is correct
36 Correct 1771 ms 17700 KB Output is correct
37 Correct 2222 ms 19432 KB Output is correct
38 Correct 2086 ms 16976 KB Output is correct
39 Correct 1909 ms 17852 KB Output is correct
40 Correct 2058 ms 17008 KB Output is correct
41 Correct 3193 ms 18804 KB Output is correct
42 Correct 3414 ms 19064 KB Output is correct