oj.uz

Submission #17076

# Submission time Handle Problem Language Result Execution time Memory
17076 2015-11-04T16:50:01 Z erdemkiraz Dancing Elephants (IOI11_elephants) C++
100 / 100
 8040 ms 23860 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];

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];
    }
    a[n] = 2 * inf;
    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)));
    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;
    }
    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 = v[0].front().second, ans = 0;
    while(pos < n) {
        if(nxt[pos] == pos) {
            ans++;
            int ind = gr[pos] + 1;
            while(ind * K < n and a[pos] + l >= v[ind].back().first)
                ind++;
            if(ind * K >= n)
                break;
            pos = lower_bound(v[ind].begin(), v[ind].end(), ii(a[pos] + l + 1, 0)) -> second;
        }
        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 20864 KB Output is correct
2 Correct 0 ms 20864 KB Output is correct
3 Correct 0 ms 20864 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1003 ms 21152 KB Output is correct
2 Correct 1043 ms 21168 KB Output is correct
3 Correct 1107 ms 21296 KB Output is correct
4 Correct 712 ms 21296 KB Output is correct
5 Correct 665 ms 21296 KB Output is correct
6 Correct 2587 ms 21456 KB Output is correct
7 Correct 744 ms 21296 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 21152 KB Output is correct
2 Correct 1426 ms 21008 KB Output is correct
3 Correct 3054 ms 21296 KB Output is correct
4 Correct 3283 ms 21584 KB Output is correct
5 Correct 3829 ms 21584 KB Output is correct
6 Correct 1647 ms 21584 KB Output is correct
7 Correct 3251 ms 21584 KB Output is correct
8 Correct 3931 ms 21584 KB Output is correct
9 Correct 1308 ms 21584 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4872 ms 22436 KB Output is correct
2 Correct 5287 ms 22436 KB Output is correct
3 Correct 3898 ms 22436 KB Output is correct
4 Correct 4394 ms 22436 KB Output is correct
5 Correct 4560 ms 22436 KB Output is correct
6 Correct 5395 ms 20864 KB Output is correct
7 Correct 5360 ms 20864 KB Output is correct
8 Correct 5422 ms 20864 KB Output is correct
9 Correct 5362 ms 20864 KB Output is correct
10 Correct 3665 ms 22436 KB Output is correct
11 Correct 2773 ms 22436 KB Output is correct
12 Correct 3682 ms 22436 KB Output is correct
13 Correct 2257 ms 22436 KB Output is correct
14 Correct 1776 ms 22436 KB Output is correct
15 Correct 6815 ms 23860 KB Output is correct
16 Correct 3800 ms 22436 KB Output is correct
17 Correct 4019 ms 22436 KB Output is correct
18 Correct 3767 ms 22436 KB Output is correct
19 Correct 8040 ms 22436 KB Output is correct
20 Correct 7789 ms 22436 KB Output is correct