oj.uz

Submission #17070

# Submission time Handle Problem Language Result Execution time Memory
17070 2015-11-04T14:35:31 Z murat Dancing Elephants (IOI11_elephants) C++
100 / 100
 6980 ms 108644 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 = 2000;
    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 13 ms 95476 KB Output is correct
2 Correct 8 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 8 ms 95476 KB Output is correct
2 Correct 8 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 562 ms 96416 KB Output is correct
2 Correct 591 ms 96944 KB Output is correct
3 Correct 678 ms 99240 KB Output is correct
4 Correct 1227 ms 99248 KB Output is correct
5 Correct 1202 ms 99248 KB Output is correct
6 Correct 1000 ms 99392 KB Output is correct
7 Correct 1270 ms 99248 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 97220 KB Output is correct
2 Correct 893 ms 97276 KB Output is correct
3 Correct 1565 ms 99384 KB Output is correct
4 Correct 1644 ms 101580 KB Output is correct
5 Correct 1713 ms 101560 KB Output is correct
6 Correct 1851 ms 101380 KB Output is correct
7 Correct 1645 ms 101584 KB Output is correct
8 Correct 1549 ms 101536 KB Output is correct
9 Correct 1924 ms 101368 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3859 ms 107780 KB Output is correct
2 Correct 4141 ms 107792 KB Output is correct
3 Correct 3409 ms 107784 KB Output is correct
4 Correct 6980 ms 107792 KB Output is correct
5 Correct 6953 ms 107804 KB Output is correct
6 Correct 2832 ms 95884 KB Output is correct
7 Correct 2839 ms 95892 KB Output is correct
8 Correct 2865 ms 95884 KB Output is correct
9 Correct 2822 ms 95892 KB Output is correct
10 Correct 4617 ms 107792 KB Output is correct
11 Correct 4048 ms 107792 KB Output is correct
12 Correct 5515 ms 107792 KB Output is correct
13 Correct 3829 ms 107792 KB Output is correct
14 Correct 1680 ms 107784 KB Output is correct
15 Correct 4756 ms 108644 KB Output is correct
16 Correct 6188 ms 107792 KB Output is correct
17 Correct 5528 ms 107804 KB Output is correct
18 Correct 6159 ms 107792 KB Output is correct
19 Correct 5009 ms 108252 KB Output is correct
20 Correct 5017 ms 108180 KB Output is correct