oj.uz

Submission #1117757

# Submission time Handle Problem Language Result Execution time Memory
1117757 2024-11-24T08:04:42 Z Mike_Vu Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2669 ms 15576 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 = 500; ///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 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 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 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 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 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 299 ms 8940 KB Output is correct
8 Correct 313 ms 9032 KB Output is correct
9 Correct 333 ms 11668 KB Output is correct
10 Correct 351 ms 11504 KB Output is correct
11 Correct 352 ms 11636 KB Output is correct
12 Correct 556 ms 11940 KB Output is correct
13 Correct 373 ms 11468 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 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 299 ms 8940 KB Output is correct
8 Correct 313 ms 9032 KB Output is correct
9 Correct 333 ms 11668 KB Output is correct
10 Correct 351 ms 11504 KB Output is correct
11 Correct 352 ms 11636 KB Output is correct
12 Correct 556 ms 11940 KB Output is correct
13 Correct 373 ms 11468 KB Output is correct
14 Correct 397 ms 9040 KB Output is correct
15 Correct 454 ms 9040 KB Output is correct
16 Correct 892 ms 11808 KB Output is correct
17 Correct 893 ms 12468 KB Output is correct
18 Correct 1012 ms 12444 KB Output is correct
19 Correct 570 ms 12004 KB Output is correct
20 Correct 905 ms 12224 KB Output is correct
21 Correct 840 ms 12224 KB Output is correct
22 Correct 616 ms 11976 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 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8528 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 1 ms 8528 KB Output is correct
7 Correct 299 ms 8940 KB Output is correct
8 Correct 313 ms 9032 KB Output is correct
9 Correct 333 ms 11668 KB Output is correct
10 Correct 351 ms 11504 KB Output is correct
11 Correct 352 ms 11636 KB Output is correct
12 Correct 556 ms 11940 KB Output is correct
13 Correct 373 ms 11468 KB Output is correct
14 Correct 397 ms 9040 KB Output is correct
15 Correct 454 ms 9040 KB Output is correct
16 Correct 892 ms 11808 KB Output is correct
17 Correct 893 ms 12468 KB Output is correct
18 Correct 1012 ms 12444 KB Output is correct
19 Correct 570 ms 12004 KB Output is correct
20 Correct 905 ms 12224 KB Output is correct
21 Correct 840 ms 12224 KB Output is correct
22 Correct 616 ms 11976 KB Output is correct
23 Correct 2263 ms 13276 KB Output is correct
24 Correct 2328 ms 13272 KB Output is correct
25 Correct 1618 ms 13276 KB Output is correct
26 Correct 2053 ms 13244 KB Output is correct
27 Correct 2056 ms 13288 KB Output is correct
28 Correct 1110 ms 8824 KB Output is correct
29 Correct 1159 ms 8820 KB Output is correct
30 Correct 1091 ms 8776 KB Output is correct
31 Correct 1132 ms 8820 KB Output is correct
32 Correct 1592 ms 13252 KB Output is correct
33 Correct 1429 ms 13244 KB Output is correct
34 Correct 1798 ms 13244 KB Output is correct
35 Correct 1441 ms 15576 KB Output is correct
36 Correct 1168 ms 13244 KB Output is correct
37 Correct 2024 ms 14576 KB Output is correct
38 Correct 1865 ms 13244 KB Output is correct
39 Correct 1753 ms 13288 KB Output is correct
40 Correct 1868 ms 13244 KB Output is correct
41 Correct 2669 ms 14084 KB Output is correct
42 Correct 2611 ms 14200 KB Output is correct