oj.uz

Submission #1085152

# Submission time Handle Problem Language Result Execution time Memory
1085152 2024-09-07T15:53:42 Z Wansur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 8882 ms 23632 KB 
#include <bits/stdc++.h>
#define ent '\n'

using namespace std;
const int maxn = 2e5 + 12;

set<pair<int, int>> s, t;
vector<int> g[maxn];
int a[maxn], block[maxn];
int out[maxn], dp[maxn];
int n, k, l, last;

void calc(vector<int> &c){
    for(int _=(int)c.size()-1;_>=0;_--){
        int i = c[_];
        assert(_ == 0 || a[i] >= a[c[_ - 1]]);
        if(a[c.back()] > a[i] + l){
            int pos = 0;
            for(int L = 0, R = (int)c.size() - 1; L <= R;){
                int mid = L + R >> 1;
                if(a[c[mid]] > a[i] + l){
                    pos = mid;
                    R = mid - 1;
                }
                else L = mid + 1;
            }
            out[i] = out[c[pos]];
            dp[i] = dp[c[pos]] + 1;
        }
        else{
            out[i] = a[i] + l;
            dp[i] = 1;
        }
        assert(out[i] >= a[i] + l);
    }
}

void init(int N, int L, int X[]){
    n = N, l = L;
    k = 700;
    for(int i=0;i<n;i++){
        a[i] = X[i];
    }
    sort(a, a+n);
    for(int i=0;i<n;i++){
        if(!g[last].size()){
            t.insert({a[i], last});
        }
        block[i] = last;
        g[last].push_back(i);
        s.insert({a[i], i});
        if(g[last].size() >= k){
            last++;
        }
    }
    for(int i=0;i<=last;i++){
        calc(g[i]);
    }
}

void del(int i){
    int pos = -1;
    for(int _=0;_<g[block[i]].size();_++){
        if(g[block[i]][_] == i){
            pos = _;
        }
    }
    if(pos < 0) exit(0);
    g[block[i]].erase(g[block[i]].begin() + pos);
    calc(g[block[i]]);
    s.erase({a[i], i});
}

void add(int i){
    auto it = t.lower_bound({a[i] + 1, 0});
    int bl = 0;
    if(it == t.begin()){
        auto [x, y] = *it;
        t.erase(it);
        t.insert({a[i], y});
        bl = y;
    }
    else{
        it--;
        bl = it -> second;
    }
    block[i] = bl;
    g[bl].push_back(i);
    sort(g[bl].begin(), g[bl].end(), [](int i, int j){
        return a[i] < a[j];
    });
    if(g[bl].size() > k){
        last++;
        while(g[bl].size() > k / 2){
            g[last].push_back(g[bl].back());
            block[g[bl].back()] = last;
            g[bl].pop_back();
        }
        reverse(g[last].begin(), g[last].end());
        t.insert({a[g[last][0]], last});
        calc(g[last]);
    }
    calc(g[bl]);
    s.insert({a[i], i});
}

int get(){
    int val = -1, ans = 0;
    while(1){
        auto it = s.lower_bound({val + 1, 0});
        if(it == s.end()) break;
        auto [x, y] = *it;
        ans += dp[y];
        val = out[y];
    }
    return ans;
}

int update(int i, int y){
    del(i);
    a[i] = y;
    add(i);
    return get();
}

Compilation message

elephants.cpp: In function 'void calc(std::vector<int>&)':
elephants.cpp:20:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |                 int mid = L + R >> 1;
      |                           ~~^~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:52:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         if(g[last].size() >= k){
      |            ~~~~~~~~~~~~~~~^~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:92:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:94:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         while(g[bl].size() > k / 2){
      |               ~~~~~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4984 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 1415 ms 7568 KB Output is correct
8 Correct 1413 ms 8040 KB Output is correct
9 Correct 1756 ms 10924 KB Output is correct
10 Correct 822 ms 11168 KB Output is correct
11 Correct 797 ms 11188 KB Output is correct
12 Correct 1831 ms 10824 KB Output is correct
13 Correct 1234 ms 11004 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4984 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 1415 ms 7568 KB Output is correct
8 Correct 1413 ms 8040 KB Output is correct
9 Correct 1756 ms 10924 KB Output is correct
10 Correct 822 ms 11168 KB Output is correct
11 Correct 797 ms 11188 KB Output is correct
12 Correct 1831 ms 10824 KB Output is correct
13 Correct 1234 ms 11004 KB Output is correct
14 Correct 1108 ms 9048 KB Output is correct
15 Correct 1237 ms 8904 KB Output is correct
16 Correct 2237 ms 11020 KB Output is correct
17 Correct 2720 ms 12608 KB Output is correct
18 Correct 3434 ms 11588 KB Output is correct
19 Correct 2988 ms 11264 KB Output is correct
20 Correct 2539 ms 11476 KB Output is correct
21 Correct 2726 ms 11092 KB Output is correct
22 Correct 2125 ms 11856 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4984 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 1415 ms 7568 KB Output is correct
8 Correct 1413 ms 8040 KB Output is correct
9 Correct 1756 ms 10924 KB Output is correct
10 Correct 822 ms 11168 KB Output is correct
11 Correct 797 ms 11188 KB Output is correct
12 Correct 1831 ms 10824 KB Output is correct
13 Correct 1234 ms 11004 KB Output is correct
14 Correct 1108 ms 9048 KB Output is correct
15 Correct 1237 ms 8904 KB Output is correct
16 Correct 2237 ms 11020 KB Output is correct
17 Correct 2720 ms 12608 KB Output is correct
18 Correct 3434 ms 11588 KB Output is correct
19 Correct 2988 ms 11264 KB Output is correct
20 Correct 2539 ms 11476 KB Output is correct
21 Correct 2726 ms 11092 KB Output is correct
22 Correct 2125 ms 11856 KB Output is correct
23 Correct 7436 ms 17772 KB Output is correct
24 Correct 8882 ms 22144 KB Output is correct
25 Correct 6324 ms 22096 KB Output is correct
26 Correct 7086 ms 23632 KB Output is correct
27 Correct 8832 ms 23376 KB Output is correct
28 Correct 2804 ms 10324 KB Output is correct
29 Incorrect 28 ms 9964 KB Output isn't correct
30 Halted 0 ms 0 KB -