제출 #1117752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117752		Mike_Vu	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	3414 ms	19844 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3