oj.uz

Submission #1085170

# Submission time Handle Problem Language Result Execution time Memory
1085170 2024-09-07T16:33:41 Z Wansur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 35924 KB 
#include <bits/stdc++.h>
#define ent '\n'

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

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

void calc(vector<int> &c){
    for(int _=(int)c.size() - 1, ptr = (int)c.size();_>=0;_--){
        int i = c[_];
        assert(_ == 0 || a[i] >= a[c[_ - 1]]);
        while(ptr > 0 && a[c[ptr - 1]] > a[i] + l){
            ptr--;
        }
        if(a[c.back()] > a[i] + l){
            out[i] = out[c[ptr]];
            dp[i] = dp[c[ptr]] + 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 = 1500;
    for(int i=0;i<n;i++){
        a[i] = X[i];
    }
    sort(a, a+n);
    for(int i=0;i<n;i++){
        q.insert({a[i], i});
        cnt[a[i]]++;
        if(cnt[a[i]] > 1) continue;
        is[i] = 1;
        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){
    q.erase({a[i], i});
    cnt[a[i]]--;
    if(cnt[a[i]] > 0){
        if(!is[i]) return;
        is[i] = 0;
        auto it = q.lower_bound({a[i], 0});
        for(int _=0;_<g[block[i]].size();_++){
            if(g[block[i]][_] == i){
                g[block[i]][_] = it -> second;
                block[it -> second] = block[i];
            }
        }
        is[it -> second] = 1;
        s.erase({a[i], i});
        s.insert(*it);
        calc(g[block[i]]);
        return;
    }
    is[i] = 0;
    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){
    q.insert({a[i], i});
    cnt[a[i]]++;
    is[i] = 0;
    if(cnt[a[i]] > 1) return;
    is[i] = 1;
    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 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:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int _=0;_<g[block[i]].size();_++){
      |                     ~^~~~~~~~~~~~~~~~~~~
elephants.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:116:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |         while(g[bl].size() > k / 2){
      |               ~~~~~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5212 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 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2324 ms 10828 KB Output is correct
8 Correct 2619 ms 11688 KB Output is correct
9 Correct 2892 ms 16464 KB Output is correct
10 Correct 997 ms 18260 KB Output is correct
11 Correct 1010 ms 18256 KB Output is correct
12 Correct 2517 ms 18004 KB Output is correct
13 Correct 1186 ms 18120 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2324 ms 10828 KB Output is correct
8 Correct 2619 ms 11688 KB Output is correct
9 Correct 2892 ms 16464 KB Output is correct
10 Correct 997 ms 18260 KB Output is correct
11 Correct 1010 ms 18256 KB Output is correct
12 Correct 2517 ms 18004 KB Output is correct
13 Correct 1186 ms 18120 KB Output is correct
14 Correct 1105 ms 11936 KB Output is correct
15 Correct 1990 ms 14416 KB Output is correct
16 Correct 2689 ms 18820 KB Output is correct
17 Correct 3063 ms 22448 KB Output is correct
18 Correct 4191 ms 22480 KB Output is correct
19 Correct 4869 ms 23268 KB Output is correct
20 Correct 3237 ms 22864 KB Output is correct
21 Correct 3946 ms 22280 KB Output is correct
22 Correct 1827 ms 22604 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2324 ms 10828 KB Output is correct
8 Correct 2619 ms 11688 KB Output is correct
9 Correct 2892 ms 16464 KB Output is correct
10 Correct 997 ms 18260 KB Output is correct
11 Correct 1010 ms 18256 KB Output is correct
12 Correct 2517 ms 18004 KB Output is correct
13 Correct 1186 ms 18120 KB Output is correct
14 Correct 1105 ms 11936 KB Output is correct
15 Correct 1990 ms 14416 KB Output is correct
16 Correct 2689 ms 18820 KB Output is correct
17 Correct 3063 ms 22448 KB Output is correct
18 Correct 4191 ms 22480 KB Output is correct
19 Correct 4869 ms 23268 KB Output is correct
20 Correct 3237 ms 22864 KB Output is correct
21 Correct 3946 ms 22280 KB Output is correct
22 Correct 1827 ms 22604 KB Output is correct
23 Execution timed out 9061 ms 35924 KB Time limit exceeded
24 Halted 0 ms 0 KB -