oj.uz

Submission #17069

# Submission time Handle Problem Language Result Execution time Memory
17069 2015-11-04T14:33:27 Z murat Dancing Elephants (IOI11_elephants) C++
100 / 100
 6190 ms 108640 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 = 2e6 + 5;

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

int SQQ, 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) {
    int ind = (int)v.size()-1;
    for(int i = (int) v.size() - 1; i >= 0; i--) {
        int zz = v[i].nd;
        while(ind >= 0 && v[ind] >= mp(v[i].st + m + 1, 0)) ind--;
        ind++;
        if(ind == v.size()) next[zz] = mp(0, i);
        else {
            int indd = v[ind].nd;
            next[zz] = mp(next[indd].st + 1, next[indd].nd);
        }
        ind--;
    }
}

void init() {
    vector< pii > ss;
    for(int i = 1; i <= S; i++) {
        foreach(it, v[i])
            ss.pb(*it);
        v[i].clear();
    }
    if(!sss) {
        for(int i = 1; i <= n; i++)
            ss.pb(mp(xx[i], i));
    }
    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]);
}

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;
    while(ww > 1 && (!v[ww].size() || *v[ww].begin() > mp(x, y))) ww--;
    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);
    SQQ = 1000;
    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 % SQQ == 0) init();
    return take();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 95504 KB Output is correct
2 Correct 8 ms 95504 KB Output is correct
3 Correct 17 ms 95504 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 95504 KB Output is correct
2 Correct 8 ms 95504 KB Output is correct
3 Correct 18 ms 95504 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 96492 KB Output is correct
2 Correct 477 ms 96972 KB Output is correct
3 Correct 701 ms 99368 KB Output is correct
4 Correct 880 ms 99268 KB Output is correct
5 Correct 729 ms 99268 KB Output is correct
6 Correct 868 ms 99408 KB Output is correct
7 Correct 970 ms 99268 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 97236 KB Output is correct
2 Correct 754 ms 97316 KB Output is correct
3 Correct 1330 ms 99412 KB Output is correct
4 Correct 1596 ms 101592 KB Output is correct
5 Correct 1656 ms 101576 KB Output is correct
6 Correct 1761 ms 101408 KB Output is correct
7 Correct 1621 ms 101600 KB Output is correct
8 Correct 1577 ms 101564 KB Output is correct
9 Correct 1627 ms 101392 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4589 ms 108160 KB Output is correct
2 Correct 4872 ms 108164 KB Output is correct
3 Correct 4207 ms 108108 KB Output is correct
4 Correct 5233 ms 107828 KB Output is correct
5 Correct 5486 ms 107832 KB Output is correct
6 Correct 737 ms 95888 KB Output is correct
7 Correct 698 ms 95904 KB Output is correct
8 Correct 729 ms 95888 KB Output is correct
9 Correct 713 ms 95904 KB Output is correct
10 Correct 3823 ms 107828 KB Output is correct
11 Correct 3333 ms 107828 KB Output is correct
12 Correct 5302 ms 107828 KB Output is correct
13 Correct 3109 ms 107828 KB Output is correct
14 Correct 1683 ms 108156 KB Output is correct
15 Correct 5353 ms 108640 KB Output is correct
16 Correct 6190 ms 107828 KB Output is correct
17 Correct 5746 ms 107832 KB Output is correct
18 Correct 5680 ms 107828 KB Output is correct
19 Correct 5479 ms 108280 KB Output is correct
20 Correct 5642 ms 108236 KB Output is correct