oj.uz

Submission #197088

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

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

vector<int> bucket[350];
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 = 850;
    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();
            r--;
            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:31: 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 0 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 0 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 0 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 1597 ms 2284 KB Output is correct
8 Correct 1614 ms 2680 KB Output is correct
9 Correct 1676 ms 3956 KB Output is correct
10 Correct 1465 ms 3700 KB Output is correct
11 Correct 1434 ms 3700 KB Output is correct
12 Correct 2338 ms 3956 KB Output is correct
13 Correct 1455 ms 3576 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 0 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 1597 ms 2284 KB Output is correct
8 Correct 1614 ms 2680 KB Output is correct
9 Correct 1676 ms 3956 KB Output is correct
10 Correct 1465 ms 3700 KB Output is correct
11 Correct 1434 ms 3700 KB Output is correct
12 Correct 2338 ms 3956 KB Output is correct
13 Correct 1455 ms 3576 KB Output is correct
14 Correct 1878 ms 3484 KB Output is correct
15 Correct 2334 ms 3448 KB Output is correct
16 Correct 3933 ms 4468 KB Output is correct
17 Correct 3732 ms 5352 KB Output is correct
18 Correct 3911 ms 5256 KB Output is correct
19 Correct 2056 ms 5360 KB Output is correct
20 Correct 3767 ms 5384 KB Output is correct
21 Correct 3535 ms 5360 KB Output is correct
22 Correct 1667 ms 4848 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 0 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 1597 ms 2284 KB Output is correct
8 Correct 1614 ms 2680 KB Output is correct
9 Correct 1676 ms 3956 KB Output is correct
10 Correct 1465 ms 3700 KB Output is correct
11 Correct 1434 ms 3700 KB Output is correct
12 Correct 2338 ms 3956 KB Output is correct
13 Correct 1455 ms 3576 KB Output is correct
14 Correct 1878 ms 3484 KB Output is correct
15 Correct 2334 ms 3448 KB Output is correct
16 Correct 3933 ms 4468 KB Output is correct
17 Correct 3732 ms 5352 KB Output is correct
18 Correct 3911 ms 5256 KB Output is correct
19 Correct 2056 ms 5360 KB Output is correct
20 Correct 3767 ms 5384 KB Output is correct
21 Correct 3535 ms 5360 KB Output is correct
22 Correct 1667 ms 4848 KB Output is correct
23 Correct 7235 ms 11464 KB Output is correct
24 Correct 7849 ms 11496 KB Output is correct
25 Correct 6489 ms 11448 KB Output is correct
26 Correct 5061 ms 11368 KB Output is correct
27 Correct 7021 ms 11456 KB Output is correct
28 Correct 7233 ms 5272 KB Output is correct
29 Correct 7160 ms 5280 KB Output is correct
30 Correct 7222 ms 5176 KB Output is correct
31 Correct 7169 ms 5284 KB Output is correct
32 Correct 5567 ms 10832 KB Output is correct
33 Correct 3694 ms 10220 KB Output is correct
34 Correct 4865 ms 11116 KB Output is correct
35 Correct 4841 ms 12260 KB Output is correct
36 Correct 5429 ms 10936 KB Output is correct
37 Correct 8728 ms 11372 KB Output is correct
38 Correct 5038 ms 10108 KB Output is correct
39 Correct 6452 ms 11116 KB Output is correct
40 Correct 5199 ms 9992 KB Output is correct
41 Execution timed out 9072 ms 11036 KB Time limit exceeded
42 Halted 0 ms 0 KB -