oj.uz

Submission #17052

# Submission time Handle Problem Language Result Execution time Memory
17052 2015-11-04T13:21:52 Z murat Dancing Elephants (IOI11_elephants) C++
97 / 100
 9000 ms 37820 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

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

#define nd second 
#define st first 

#define next sadas

const int inf = 1e9 + 5;
const int N = 2e5 + 5;

int SQ;
typedef pair< int , int > pii;
typedef long long ll;

int sss, n, m, x, y, z, t, S, xx[N], wh[N];
pii next[N];
vector< pii > v[N];
set< pii > SS;

pii take(int ind, int w) {
    int t = 0, ss = v[w][ind].st;
    while(w <= S && (!v[w].size() || (v[w].rbegin()->st) <= ss + m)) w++;
    if(w > S) return mp(inf + 5, inf + 5);
    return mp(lower_bound(v[w].begin(), v[w].end(), mp(ss + m + 1, 0)) - v[w].begin(), w);
}

int take() {
    pii cur = mp(0, 1);
    int ans = 0;
    while(!v[cur.nd].size()) cur.nd++;
    while(cur.nd < inf) {
        int u = v[cur.nd][cur.st].nd;
        if(next[u].st) { ans += next[u].st; cur.st = next[u].nd; }
        else { cur = take(cur.st, cur.nd); ans++; }
    }
    return ans;
}

void init(vector< pii > &v) {
    for(int i = (int) v.size() - 1; i >= 0; i--) {
        int zz = v[i].nd, ind = upper_bound(v.begin(), v.end(), mp(v[i].st + m, inf)) - v.begin();
        if(ind == v.size()) next[zz] = mp(0, i);
        else {
            ind = v[ind].nd;
            next[zz] = mp(next[ind].st + 1, next[ind].nd);
        }
    }
}

void init() {
    vector< pii > ss;
    for(int i = 1; i <= S; i++) {
        foreach(it, v[i])
            ss.pb(*it);
        v[i].clear();
    }
    if(!sss) {
        foreach(it, SS)
            ss.pb(*it);
    }
    int s = 0; S = 0;
    vector< pii > :: iterator it2 = ss.end(); it2--;
    vector< pii > temp;
    foreach(it, ss) {
        temp.pb(*it);
        if(++s % SQ == 0 || (it == it2)) {
            v[++S] = temp;
            foreach(it, temp) wh[it->nd] = S;
            init(v[S]);
            temp.clear();
        }
    }
    ss.clear();
}

void del(int x, int y) {
    int ww = wh[y];
    v[ww].erase(find(v[ww].begin(), v[ww].end(), mp(x, y)));
    init(v[ww]);
    SS.erase(SS.find(mp(x, y)));
}

void ins(vector< pii > &v, pii x) {
    vector< pii > temp;
    int t = 0;
    foreach(it, v) {
        if(!t && *it > x) { temp.pb(x); t = 1; }
        temp.pb(*it);
    }if(!t) temp.pb(x);
    v = temp;
    temp.clear();
}

void add(int x, int y) {
    int ww = S;
    if(SS.lower_bound(mp(x, y)) != SS.end())
        ww = wh[SS.lower_bound(mp(x, y))->nd];
    SS.insert(mp(x, y));
    wh[y] = ww;
    ins(v[ww], mp(x, y));
    init(v[ww]);
}

void init(int N, int L, int X[]) {
    n = N;
    m = L;
    SQ = sqrt(N);
    for(int i = 0; i < n; i++) {
        xx[i+1] = X[i];
        SS.insert(mp(X[i], i+1));
    }
    init();
}

int update(int i, int y) {
    i++;
    del(xx[i], i);
    add(xx[i] = y, i);
    if(++sss % SQ == 0) init();
    return take();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 26248 KB Output is correct
2 Correct 1220 ms 26832 KB Output is correct
3 Correct 1390 ms 29064 KB Output is correct
4 Correct 1311 ms 28952 KB Output is correct
5 Correct 1133 ms 28952 KB Output is correct
6 Correct 2414 ms 29084 KB Output is correct
7 Correct 1348 ms 28952 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1106 ms 26760 KB Output is correct
2 Correct 1881 ms 27004 KB Output is correct
3 Correct 3596 ms 29092 KB Output is correct
4 Correct 4641 ms 31268 KB Output is correct
5 Correct 4594 ms 31260 KB Output is correct
6 Correct 3821 ms 31072 KB Output is correct
7 Correct 4647 ms 31260 KB Output is correct
8 Correct 4342 ms 31252 KB Output is correct
9 Correct 2342 ms 31072 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 37820 KB Program timed out
2 Halted 0 ms 0 KB -