oj.uz

Submission #17071

# Submission time Handle Problem Language Result Execution time Memory
17071 2015-11-04T14:38:34 Z murat Dancing Elephants (IOI11_elephants) C++
100 / 100
 5604 ms 108528 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 = 500;
    SQQ = 700;
    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 5 ms 95476 KB Output is correct
2 Correct 12 ms 95476 KB Output is correct
3 Correct 8 ms 95476 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 95476 KB Output is correct
2 Correct 21 ms 95476 KB Output is correct
3 Correct 10 ms 95476 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 96416 KB Output is correct
2 Correct 613 ms 96944 KB Output is correct
3 Correct 745 ms 99236 KB Output is correct
4 Correct 891 ms 99244 KB Output is correct
5 Correct 850 ms 99244 KB Output is correct
6 Correct 1058 ms 99392 KB Output is correct
7 Correct 960 ms 99244 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 97096 KB Output is correct
2 Correct 932 ms 97276 KB Output is correct
3 Correct 1698 ms 99384 KB Output is correct
4 Correct 1750 ms 101588 KB Output is correct
5 Correct 1817 ms 101592 KB Output is correct
6 Correct 1455 ms 101368 KB Output is correct
7 Correct 1753 ms 101588 KB Output is correct
8 Correct 1630 ms 101528 KB Output is correct
9 Correct 1539 ms 101364 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4256 ms 107780 KB Output is correct
2 Correct 4693 ms 107788 KB Output is correct
3 Correct 3842 ms 107780 KB Output is correct
4 Correct 5500 ms 107788 KB Output is correct
5 Correct 5471 ms 107792 KB Output is correct
6 Correct 2746 ms 95844 KB Output is correct
7 Correct 2686 ms 95860 KB Output is correct
8 Correct 2768 ms 95844 KB Output is correct
9 Correct 2669 ms 95860 KB Output is correct
10 Correct 3803 ms 107788 KB Output is correct
11 Correct 3337 ms 107788 KB Output is correct
12 Correct 4779 ms 107788 KB Output is correct
13 Correct 3154 ms 107788 KB Output is correct
14 Correct 2012 ms 107780 KB Output is correct
15 Correct 5285 ms 108528 KB Output is correct
16 Correct 5363 ms 107788 KB Output is correct
17 Correct 4806 ms 107792 KB Output is correct
18 Correct 5276 ms 107788 KB Output is correct
19 Correct 5572 ms 108212 KB Output is correct
20 Correct 5604 ms 108196 KB Output is correct