oj.uz

Submission #197090

# Submission time Handle Problem Language Result Execution time Memory
197090 2020-01-18T14:58:31 Z stefdasca Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 6508 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;
int sqt = 0;
int n, L;
int V[150005];

vector<int> bucket[600];
int DP[150005];
int G[150005];
int pos[150005];
int lastbucket = 0;
int pot = 0;
vector<int> v(n);
void rebuild(bool C)
{
    pot = 0;
    if(C)
        for(int i = 0; i < n; i++)
            v.push_back(i);
    else
    {
        v.clear();
        int last = -1;
        for(int i = 0; i <= lastbucket; i++)
        {
            for(int j = 0; j < bucket[i].size(); j++)
            {
                v.push_back(bucket[i][j]);
                last = bucket[i][j];
            }
            bucket[i].clear();
        }
    }
    int currbucket = 0;
    for(int i = 0; i < n; i++)
    {
        if(bucket[currbucket].size() <= sqt)
            bucket[currbucket].push_back(v[i]);
        else
            bucket[++currbucket].push_back(v[i]);
        pos[v[i]] = currbucket;
        lastbucket = currbucket;
    }
    for(int i = 0; i <= lastbucket; i++)
    {
        int curr = 0;
        int X = bucket[i].size();
        curr = X-1;
        for(int j = X - 1; j >= 0; j--)
        {
            DP[bucket[i][j]] = 1;
            while(curr > j && V[bucket[i][curr - 1]] > (V[bucket[i][j]] + L))
                curr--;
            G[bucket[i][j]] = j;
            if(V[bucket[i][curr]] > (V[bucket[i][j]] + L))
            {
                DP[bucket[i][j]] += DP[bucket[i][curr]];
                G[bucket[i][j]] = G[bucket[i][curr]];
            }
        }
    }
}

void erase_elem(int currbucket, int vl)
{
    vector<int> w;
    for(int i = 0; i < bucket[currbucket].size(); i++)
    {
        if(bucket[currbucket][i] == vl)
            continue;
        w.push_back(bucket[currbucket][i]);
    }
    bucket[currbucket] = w;
    int i = currbucket;
    int X = bucket[i].size();
    int curr = X-1;
    for(int j = X - 1; j >= 0; j--)
    {
        DP[bucket[i][j]] = 1;
        while(curr > j && V[bucket[i][curr - 1]] > (V[bucket[i][j]] + L))
            curr--;
        G[bucket[i][j]] = j;
        if(V[bucket[i][curr]] > (V[bucket[i][j]] + L))
        {
            DP[bucket[i][j]] += DP[bucket[i][curr]];
            G[bucket[i][j]] = G[bucket[i][curr]];
        }
    }
}

void add_elem(int currbucket, int vl)
{
    vector<int> w;
    bool gone = 0;
    pos[vl] = currbucket;
    for(int i = 0; i < bucket[currbucket].size(); i++)
    {
        if(V[bucket[currbucket][i]] >= V[vl] && !gone)
        {
            gone = 1;
            w.push_back(vl);
        }
        w.push_back(bucket[currbucket][i]);
    }
    if(!gone)
        w.push_back(vl);
    swap(bucket[currbucket], w);
    int i = currbucket;
    int X = bucket[i].size();
    int curr = X - 1;
    for(int j = X - 1; j >= 0; j--)
    {
        DP[bucket[i][j]] = 1;
        while(curr > j && V[bucket[i][curr - 1]] > (V[bucket[i][j]] + L))
            curr--;
        G[bucket[i][j]] = j;
        if(V[bucket[i][curr]] > (V[bucket[i][j]] + L))
        {
            DP[bucket[i][j]] += DP[bucket[i][curr]];
            G[bucket[i][j]] = G[bucket[i][curr]];
        }
    }
}

void init(int N, int Lx, int X[])
{
    sqt = 400;
    n = N;
    L = Lx;
    for(int i = 0; i < N ; i++)
        V[i] = X[i];
    rebuild(1);
}

int update(int ix, int yx)
{
    erase_elem(pos[ix],ix);
    int oldd = pos[ix];
    V[ix] = yx;
    int newbucket = lastbucket;
    for(int i = 0; i < lastbucket; i++)
        if(bucket[i+1].size() && V[bucket[i+1].front()] >= yx)
        {
            newbucket = i;
            break;
        }
    add_elem(newbucket, ix);
    pot++;
    if(bucket[oldd].size() == 0 || pot >= sqt)
        rebuild(0);
    int currpos = 0;
    int currbucket = 0;
    int ans = 0;
    while(1)
    {
        ans += DP[bucket[currbucket][currpos]];
        currpos = G[bucket[currbucket][currpos]];
        int ansj = -1;
        int R = V[bucket[currbucket][currpos]] + L;
        for(int j = currbucket + 1; j <= lastbucket; j++)
        {
            if(V[bucket[j].back()] <= R)
                continue;
            else
            {
                ansj = j;
                break;
            }
        }
        if(ansj == -1)
            break;
        else
        {
            currbucket = ansj;
            int l = 0, r = bucket[currbucket].size() - 1;
            int ansj2 = -1;
            while(l <= r)
            {
                int mid = (l + r) / 2;
                if(V[bucket[ansj][mid]] > R)
                {
                    r = mid - 1;
                    ansj2 = mid;
                }
                else
                    l = mid + 1;
            }
            currpos = ansj2;
        }
    }
    return ans;

}

Compilation message

elephants.cpp: In function 'void rebuild(bool)':
elephants.cpp:28:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < bucket[i].size(); j++)
                            ~~^~~~~~~~~~~~~~~~~~
elephants.cpp:25:13: warning: variable 'last' set but not used [-Wunused-but-set-variable]
         int last = -1;
             ^~~~
elephants.cpp:39:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(bucket[currbucket].size() <= sqt)
            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
elephants.cpp: In function 'void erase_elem(int, int)':
elephants.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < bucket[currbucket].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add_elem(int, int)':
elephants.cpp:98:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < bucket[currbucket].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 860 ms 1400 KB Output is correct
8 Correct 970 ms 1528 KB Output is correct
9 Correct 1129 ms 2520 KB Output is correct
10 Correct 997 ms 2420 KB Output is correct
11 Correct 885 ms 2420 KB Output is correct
12 Correct 1526 ms 2420 KB Output is correct
13 Correct 985 ms 2420 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 860 ms 1400 KB Output is correct
8 Correct 970 ms 1528 KB Output is correct
9 Correct 1129 ms 2520 KB Output is correct
10 Correct 997 ms 2420 KB Output is correct
11 Correct 885 ms 2420 KB Output is correct
12 Correct 1526 ms 2420 KB Output is correct
13 Correct 985 ms 2420 KB Output is correct
14 Correct 1095 ms 1928 KB Output is correct
15 Correct 1355 ms 1936 KB Output is correct
16 Correct 2471 ms 2804 KB Output is correct
17 Correct 2661 ms 3292 KB Output is correct
18 Correct 2768 ms 3312 KB Output is correct
19 Correct 1900 ms 3312 KB Output is correct
20 Correct 2671 ms 3404 KB Output is correct
21 Correct 2564 ms 3180 KB Output is correct
22 Correct 1696 ms 3308 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 860 ms 1400 KB Output is correct
8 Correct 970 ms 1528 KB Output is correct
9 Correct 1129 ms 2520 KB Output is correct
10 Correct 997 ms 2420 KB Output is correct
11 Correct 885 ms 2420 KB Output is correct
12 Correct 1526 ms 2420 KB Output is correct
13 Correct 985 ms 2420 KB Output is correct
14 Correct 1095 ms 1928 KB Output is correct
15 Correct 1355 ms 1936 KB Output is correct
16 Correct 2471 ms 2804 KB Output is correct
17 Correct 2661 ms 3292 KB Output is correct
18 Correct 2768 ms 3312 KB Output is correct
19 Correct 1900 ms 3312 KB Output is correct
20 Correct 2671 ms 3404 KB Output is correct
21 Correct 2564 ms 3180 KB Output is correct
22 Correct 1696 ms 3308 KB Output is correct
23 Correct 7287 ms 6508 KB Output is correct
24 Correct 7570 ms 6488 KB Output is correct
25 Correct 6800 ms 6348 KB Output is correct
26 Correct 6050 ms 6472 KB Output is correct
27 Execution timed out 9081 ms 6380 KB Time limit exceeded
28 Halted 0 ms 0 KB -