oj.uz

Submission #17075

# Submission time Handle Problem Language Result Execution time Memory
17075 2015-11-04T16:16:11 Z erdemkiraz Dancing Elephants (IOI11_elephants) C++
97 / 100
 9000 ms 29436 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 150000 + 5;
const int K = 1500;
const int T = N / K + 5;

int n, l;
int a[N], gr[N], nxt[N], need[N];
vector < ii > v[T];
set < ii > all;

inline int get(int x) {
    return all.lower_bound(ii(x + l + 1, 0)) -> second;
}

void rebuild(int i) {
    int last = 0;
    if(v[i].size())
        last = v[i].back().first;
    int pos = (int) v[i].size() - 1;
    for(int j = (int) v[i].size() - 1; j >= 0; j--) {
        int x = v[i][j].first;
        int id = v[i][j].second;
        gr[id] = i;
        if(x + l >= last) {
            nxt[id] = id;
            need[id] = 0;
        }
        else {
            while(pos > j + 1 and x + l < v[i][pos - 1].first)
                pos--;
            nxt[id] = nxt[v[i][pos].second];
            need[id] = need[v[i][pos].second] + 1;
        }
    }
}

ii b[N];

void init(bool flag = 0) {
    if(flag) {
        for(int i = 0; i < n; i++)
            b[i] = ii(a[i], i);
    }
    else {
        int sz = 0;
        for(int i = 0; i * K < n; i++) {
            for(int j = 0; j < v[i].size(); j++)
                b[sz++] = v[i][j];
        }
    }
    int ind = 0;
    for(int i = 0; i * K < n; i++) {
        v[i].clear();
        for(int j = i * K; j < n and j < (i + 1) * K; j++) {
            v[i].push_back(b[j]);
        }
        ind = i;
    }
    for(int i = ind; i >= 0; i--)
        rebuild(i);
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    for(int i = 0; i < n; i++) {
        a[i] = X[i];
        all.insert(ii(a[i], i));
    }
    a[n] = 2 * inf;
    all.insert(ii(2 * inf, n));
    init(1);
}

int upCnt = 0;

int update(int i, int x) {
    int ind = gr[i];
    v[ind].erase(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i)));
    all.erase(ii(a[i], i));
    rebuild(ind);
    a[i] = x;
    for(int j = 0; j * K < n; j++) {
        ind = j;
        if(v[j].size() and ii(a[i], i) <= v[j].back())
            break;
    }
    all.insert(ii(a[i], i));
    v[ind].insert(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i)), ii(a[i], i));
    rebuild(ind);
    upCnt++;
    if(upCnt == 1500) {
        upCnt = 0;
        init();
    }
    int pos = all.begin() -> second, ans = 0;
    while(pos < n) {
        if(nxt[pos] == pos) {
            ans++;
            pos = get(a[pos]);
        }
        else {
            ans += need[pos];
            pos = nxt[pos];
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 21680 KB Output is correct
2 Correct 1078 ms 21960 KB Output is correct
3 Correct 1301 ms 23676 KB Output is correct
4 Correct 915 ms 23676 KB Output is correct
5 Correct 941 ms 23676 KB Output is correct
6 Correct 2907 ms 23676 KB Output is correct
7 Correct 1099 ms 23676 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 21944 KB Output is correct
2 Correct 1518 ms 22204 KB Output is correct
3 Correct 3535 ms 23676 KB Output is correct
4 Correct 4002 ms 24888 KB Output is correct
5 Correct 4609 ms 24888 KB Output is correct
6 Correct 2308 ms 24888 KB Output is correct
7 Correct 3974 ms 24888 KB Output is correct
8 Correct 4651 ms 24888 KB Output is correct
9 Correct 2118 ms 24888 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8498 ms 29436 KB Output is correct
2 Execution timed out 9000 ms 29436 KB Program timed out
3 Halted 0 ms 0 KB -