oj.uz

Submission #197102

# Submission time Handle Problem Language Result Execution time Memory
197102 2020-01-18T15:45:35 Z stefdasca Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6065 ms 13296 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

int n, l, *x, uc, bc, r[302];
map<int, int> mp;
vector<int> v[302];
vector<array<int, 2>> w[302];

void init(int N, int L, int X[])
{
    n=N, l=L, x=X;
    for(int i=0; i<n; ++i)
        ++mp[x[i]];
}

void bb(int i)
{
    w[i]=vector<array<int, 2>>(v[i].size());
    for(int j1=(int)v[i].size()-1, j2=v[i].size(); ~j1; --j1)
    {
        while(v[i][j2-1]>v[i][j1]+l)
            --j2;
        if(j2<v[i].size())
            w[i][j1]= array<int, 2> {w[i][j2][0]+1, w[i][j2][1]};
        else
            w[i][j1]= array<int, 2> {1, v[i][j1]+l};
    }
}
void bld()
{
    bc=0;
    for(pair<int, int> p : mp)
    {
        if(!bc || v[bc-1].size()>=550)
            v[bc++].clear();
        v[bc-1].push_back(p.first);
    }
    for(int i=0; i<bc; ++i)
    {
        if(i+1 < bc)
            r[i]=v[i+1][0]-1;
        else
            r[i] = 1000000000;
        bb(i);
    }
}

void upd(int x, bool a)
{
    int c=-1;
    while(x>r[++c]);
    int p=lower_bound(v[c].begin(), v[c].end(), x)-v[c].begin();
    if(a)
        v[c].insert(v[c].begin()+p, x);
    else
        v[c].erase(v[c].begin()+p);
    bb(c);
}

int update(int i, int y)
{
    if(uc++ % 550 ==0)
        bld();
    --mp[x[i]];
    if(!mp[x[i]])
    {
        upd(x[i], 0);
        mp.erase(x[i]);
    }
    if(!mp[y])
        upd(y, 1);
    ++mp[y];
    x[i]=y;
    int a=0;
    for(int i=0, c=-1; i<bc; ++i)
    {
        int p=upper_bound(v[i].begin(), v[i].end(), c)-v[i].begin();
        if(p<v[i].size())
        {
            a+=w[i][p][0];
            c=w[i][p][1];
        }
    }
    return a;
}

Compilation message

elephants.cpp: In function 'void bb(int)':
elephants.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(j2<v[i].size())
            ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:79:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(p<v[i].size())
            ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 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 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 4 ms 504 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 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 343 ms 2608 KB Output is correct
8 Correct 344 ms 2412 KB Output is correct
9 Correct 520 ms 4984 KB Output is correct
10 Correct 499 ms 5116 KB Output is correct
11 Correct 542 ms 4728 KB Output is correct
12 Correct 893 ms 5384 KB Output is correct
13 Correct 516 ms 5112 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 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 343 ms 2608 KB Output is correct
8 Correct 344 ms 2412 KB Output is correct
9 Correct 520 ms 4984 KB Output is correct
10 Correct 499 ms 5116 KB Output is correct
11 Correct 542 ms 4728 KB Output is correct
12 Correct 893 ms 5384 KB Output is correct
13 Correct 516 ms 5112 KB Output is correct
14 Correct 287 ms 3524 KB Output is correct
15 Correct 605 ms 3304 KB Output is correct
16 Correct 1321 ms 5412 KB Output is correct
17 Correct 1492 ms 6628 KB Output is correct
18 Correct 1643 ms 7032 KB Output is correct
19 Correct 874 ms 6648 KB Output is correct
20 Correct 1829 ms 6864 KB Output is correct
21 Correct 1446 ms 6776 KB Output is correct
22 Correct 774 ms 6776 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 343 ms 2608 KB Output is correct
8 Correct 344 ms 2412 KB Output is correct
9 Correct 520 ms 4984 KB Output is correct
10 Correct 499 ms 5116 KB Output is correct
11 Correct 542 ms 4728 KB Output is correct
12 Correct 893 ms 5384 KB Output is correct
13 Correct 516 ms 5112 KB Output is correct
14 Correct 287 ms 3524 KB Output is correct
15 Correct 605 ms 3304 KB Output is correct
16 Correct 1321 ms 5412 KB Output is correct
17 Correct 1492 ms 6628 KB Output is correct
18 Correct 1643 ms 7032 KB Output is correct
19 Correct 874 ms 6648 KB Output is correct
20 Correct 1829 ms 6864 KB Output is correct
21 Correct 1446 ms 6776 KB Output is correct
22 Correct 774 ms 6776 KB Output is correct
23 Correct 4159 ms 12984 KB Output is correct
24 Correct 3901 ms 13032 KB Output is correct
25 Correct 3276 ms 12464 KB Output is correct
26 Correct 3018 ms 13004 KB Output is correct
27 Correct 3240 ms 12916 KB Output is correct
28 Correct 1997 ms 3592 KB Output is correct
29 Correct 1839 ms 3480 KB Output is correct
30 Correct 1948 ms 3704 KB Output is correct
31 Correct 1832 ms 3432 KB Output is correct
32 Correct 3508 ms 12612 KB Output is correct
33 Correct 1405 ms 13064 KB Output is correct
34 Correct 2943 ms 12536 KB Output is correct
35 Correct 1570 ms 12920 KB Output is correct
36 Correct 80 ms 3628 KB Output is correct
37 Correct 2472 ms 13296 KB Output is correct
38 Correct 2965 ms 12876 KB Output is correct
39 Correct 3236 ms 12664 KB Output is correct
40 Correct 3199 ms 12996 KB Output is correct
41 Correct 5677 ms 13256 KB Output is correct
42 Correct 6065 ms 12556 KB Output is correct