oj.uz

Submission #197091

# Submission time Handle Problem Language Result Execution time Memory
197091 2020-01-18T15:01:07 Z stefdasca Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 7436 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 = 1000;
    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 3 ms 380 KB Output is correct
2 Correct 2 ms 372 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 3 ms 380 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 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 3 ms 380 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1874 ms 1384 KB Output is correct
8 Correct 1871 ms 1528 KB Output is correct
9 Correct 1920 ms 2464 KB Output is correct
10 Correct 1810 ms 2420 KB Output is correct
11 Correct 1646 ms 2420 KB Output is correct
12 Correct 2707 ms 2612 KB Output is correct
13 Correct 1769 ms 2296 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1874 ms 1384 KB Output is correct
8 Correct 1871 ms 1528 KB Output is correct
9 Correct 1920 ms 2464 KB Output is correct
10 Correct 1810 ms 2420 KB Output is correct
11 Correct 1646 ms 2420 KB Output is correct
12 Correct 2707 ms 2612 KB Output is correct
13 Correct 1769 ms 2296 KB Output is correct
14 Correct 2150 ms 2064 KB Output is correct
15 Correct 2696 ms 1808 KB Output is correct
16 Correct 4410 ms 2548 KB Output is correct
17 Correct 4192 ms 3356 KB Output is correct
18 Correct 4413 ms 3244 KB Output is correct
19 Correct 2615 ms 3184 KB Output is correct
20 Correct 4210 ms 3444 KB Output is correct
21 Correct 4010 ms 3348 KB Output is correct
22 Correct 2584 ms 3156 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1874 ms 1384 KB Output is correct
8 Correct 1871 ms 1528 KB Output is correct
9 Correct 1920 ms 2464 KB Output is correct
10 Correct 1810 ms 2420 KB Output is correct
11 Correct 1646 ms 2420 KB Output is correct
12 Correct 2707 ms 2612 KB Output is correct
13 Correct 1769 ms 2296 KB Output is correct
14 Correct 2150 ms 2064 KB Output is correct
15 Correct 2696 ms 1808 KB Output is correct
16 Correct 4410 ms 2548 KB Output is correct
17 Correct 4192 ms 3356 KB Output is correct
18 Correct 4413 ms 3244 KB Output is correct
19 Correct 2615 ms 3184 KB Output is correct
20 Correct 4210 ms 3444 KB Output is correct
21 Correct 4010 ms 3348 KB Output is correct
22 Correct 2584 ms 3156 KB Output is correct
23 Correct 7748 ms 6252 KB Output is correct
24 Correct 8204 ms 6244 KB Output is correct
25 Correct 6929 ms 6252 KB Output is correct
26 Correct 7139 ms 6248 KB Output is correct
27 Correct 7220 ms 6252 KB Output is correct
28 Correct 8173 ms 2552 KB Output is correct
29 Correct 8114 ms 2728 KB Output is correct
30 Correct 8238 ms 2720 KB Output is correct
31 Correct 8109 ms 2760 KB Output is correct
32 Correct 5986 ms 6764 KB Output is correct
33 Correct 5291 ms 6780 KB Output is correct
34 Correct 6430 ms 6672 KB Output is correct
35 Correct 5635 ms 7436 KB Output is correct
36 Correct 6307 ms 6696 KB Output is correct
37 Execution timed out 9031 ms 6748 KB Time limit exceeded
38 Halted 0 ms 0 KB -