oj.uz

Submission #1085194

# Submission time Handle Problem Language Result Execution time Memory
1085194 2024-09-07T16:46:24 Z Wansur Dancing Elephants (IOI11_elephants) C++17
100 / 100
 6109 ms 45580 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[_];
        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;
        }
    }
}

void init(int N, int L, int X[]){
    n = N, l = L;
    k = 1300;
    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;
    vector<int> nw;
    bool ok = 0;
    for(int x:g[bl]){
        if(!ok && a[x] > a[i]){
            nw.push_back(i);
            ok = 1;
        }
        nw.push_back(x);
    }
    if(!ok) nw.push_back(i);
    nw.swap(g[bl]);
    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:50:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         if(g[last].size() >= k){
      |            ~~~~~~~~~~~~~~~^~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int _=0;_<g[block[i]].size();_++){
      |                     ~^~~~~~~~~~~~~~~~~~~
elephants.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:121:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:123:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |         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 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 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 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 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 490 ms 10832 KB Output is correct
8 Correct 516 ms 12164 KB Output is correct
9 Correct 636 ms 16468 KB Output is correct
10 Correct 527 ms 18424 KB Output is correct
11 Correct 565 ms 18296 KB Output is correct
12 Correct 1025 ms 17780 KB Output is correct
13 Correct 747 ms 18232 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 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 490 ms 10832 KB Output is correct
8 Correct 516 ms 12164 KB Output is correct
9 Correct 636 ms 16468 KB Output is correct
10 Correct 527 ms 18424 KB Output is correct
11 Correct 565 ms 18296 KB Output is correct
12 Correct 1025 ms 17780 KB Output is correct
13 Correct 747 ms 18232 KB Output is correct
14 Correct 374 ms 11976 KB Output is correct
15 Correct 549 ms 14192 KB Output is correct
16 Correct 1321 ms 18564 KB Output is correct
17 Correct 1501 ms 22096 KB Output is correct
18 Correct 1892 ms 22356 KB Output is correct
19 Correct 778 ms 23376 KB Output is correct
20 Correct 1584 ms 22608 KB Output is correct
21 Correct 1649 ms 22676 KB Output is correct
22 Correct 1269 ms 23376 KB Output is correct

Subtask #5
3.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 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 490 ms 10832 KB Output is correct
8 Correct 516 ms 12164 KB Output is correct
9 Correct 636 ms 16468 KB Output is correct
10 Correct 527 ms 18424 KB Output is correct
11 Correct 565 ms 18296 KB Output is correct
12 Correct 1025 ms 17780 KB Output is correct
13 Correct 747 ms 18232 KB Output is correct
14 Correct 374 ms 11976 KB Output is correct
15 Correct 549 ms 14192 KB Output is correct
16 Correct 1321 ms 18564 KB Output is correct
17 Correct 1501 ms 22096 KB Output is correct
18 Correct 1892 ms 22356 KB Output is correct
19 Correct 778 ms 23376 KB Output is correct
20 Correct 1584 ms 22608 KB Output is correct
21 Correct 1649 ms 22676 KB Output is correct
22 Correct 1269 ms 23376 KB Output is correct
23 Correct 3452 ms 40532 KB Output is correct
24 Correct 3067 ms 39088 KB Output is correct
25 Correct 2659 ms 38908 KB Output is correct
26 Correct 2544 ms 44900 KB Output is correct
27 Correct 2541 ms 44112 KB Output is correct
28 Correct 1394 ms 14696 KB Output is correct
29 Correct 1385 ms 14172 KB Output is correct
30 Correct 1431 ms 14676 KB Output is correct
31 Correct 1360 ms 14440 KB Output is correct
32 Correct 3591 ms 45240 KB Output is correct
33 Correct 1989 ms 36440 KB Output is correct
34 Correct 2617 ms 45580 KB Output is correct
35 Correct 926 ms 36944 KB Output is correct
36 Correct 126 ms 19516 KB Output is correct
37 Correct 1493 ms 36944 KB Output is correct
38 Correct 5435 ms 44368 KB Output is correct
39 Correct 3286 ms 44732 KB Output is correct
40 Correct 5566 ms 44480 KB Output is correct
41 Correct 5956 ms 42204 KB Output is correct
42 Correct 6109 ms 42832 KB Output is correct