oj.uz

Submission #1085151

# Submission time Handle Problem Language Result Execution time Memory
1085151 2024-09-07T15:53:10 Z Wansur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 21520 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 = 1000;
    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 4956 KB Output is correct
3 Correct 3 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 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 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 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2263 ms 6632 KB Output is correct
8 Correct 2382 ms 7000 KB Output is correct
9 Correct 2523 ms 9280 KB Output is correct
10 Correct 1120 ms 9548 KB Output is correct
11 Correct 1067 ms 9556 KB Output is correct
12 Correct 2686 ms 9432 KB Output is correct
13 Correct 1357 ms 9552 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 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2263 ms 6632 KB Output is correct
8 Correct 2382 ms 7000 KB Output is correct
9 Correct 2523 ms 9280 KB Output is correct
10 Correct 1120 ms 9548 KB Output is correct
11 Correct 1067 ms 9556 KB Output is correct
12 Correct 2686 ms 9432 KB Output is correct
13 Correct 1357 ms 9552 KB Output is correct
14 Correct 1535 ms 7572 KB Output is correct
15 Correct 1731 ms 8536 KB Output is correct
16 Correct 3171 ms 10764 KB Output is correct
17 Correct 3231 ms 12528 KB Output is correct
18 Correct 4769 ms 12268 KB Output is correct
19 Correct 3868 ms 13136 KB Output is correct
20 Correct 3436 ms 13204 KB Output is correct
21 Correct 4363 ms 12856 KB Output is correct
22 Correct 2191 ms 13036 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 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2263 ms 6632 KB Output is correct
8 Correct 2382 ms 7000 KB Output is correct
9 Correct 2523 ms 9280 KB Output is correct
10 Correct 1120 ms 9548 KB Output is correct
11 Correct 1067 ms 9556 KB Output is correct
12 Correct 2686 ms 9432 KB Output is correct
13 Correct 1357 ms 9552 KB Output is correct
14 Correct 1535 ms 7572 KB Output is correct
15 Correct 1731 ms 8536 KB Output is correct
16 Correct 3171 ms 10764 KB Output is correct
17 Correct 3231 ms 12528 KB Output is correct
18 Correct 4769 ms 12268 KB Output is correct
19 Correct 3868 ms 13136 KB Output is correct
20 Correct 3436 ms 13204 KB Output is correct
21 Correct 4363 ms 12856 KB Output is correct
22 Correct 2191 ms 13036 KB Output is correct
23 Execution timed out 9045 ms 21520 KB Time limit exceeded
24 Halted 0 ms 0 KB -