oj.uz

Submission #1085193

# Submission time Handle Problem Language Result Execution time Memory
1085193 2024-09-07T16:44:55 Z Wansur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 45228 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 = 800;
    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 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 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 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5152 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 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5152 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 361 ms 10832 KB Output is correct
8 Correct 383 ms 11860 KB Output is correct
9 Correct 505 ms 16424 KB Output is correct
10 Correct 475 ms 18264 KB Output is correct
11 Correct 540 ms 18084 KB Output is correct
12 Correct 894 ms 18000 KB Output is correct
13 Correct 881 ms 18000 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5152 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 361 ms 10832 KB Output is correct
8 Correct 383 ms 11860 KB Output is correct
9 Correct 505 ms 16424 KB Output is correct
10 Correct 475 ms 18264 KB Output is correct
11 Correct 540 ms 18084 KB Output is correct
12 Correct 894 ms 18000 KB Output is correct
13 Correct 881 ms 18000 KB Output is correct
14 Correct 297 ms 11860 KB Output is correct
15 Correct 458 ms 14160 KB Output is correct
16 Correct 1105 ms 18512 KB Output is correct
17 Correct 1370 ms 22356 KB Output is correct
18 Correct 1505 ms 22504 KB Output is correct
19 Correct 845 ms 23420 KB Output is correct
20 Correct 1537 ms 22868 KB Output is correct
21 Correct 1414 ms 22864 KB Output is correct
22 Correct 1585 ms 23120 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5152 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 361 ms 10832 KB Output is correct
8 Correct 383 ms 11860 KB Output is correct
9 Correct 505 ms 16424 KB Output is correct
10 Correct 475 ms 18264 KB Output is correct
11 Correct 540 ms 18084 KB Output is correct
12 Correct 894 ms 18000 KB Output is correct
13 Correct 881 ms 18000 KB Output is correct
14 Correct 297 ms 11860 KB Output is correct
15 Correct 458 ms 14160 KB Output is correct
16 Correct 1105 ms 18512 KB Output is correct
17 Correct 1370 ms 22356 KB Output is correct
18 Correct 1505 ms 22504 KB Output is correct
19 Correct 845 ms 23420 KB Output is correct
20 Correct 1537 ms 22868 KB Output is correct
21 Correct 1414 ms 22864 KB Output is correct
22 Correct 1585 ms 23120 KB Output is correct
23 Correct 3515 ms 41232 KB Output is correct
24 Correct 3393 ms 39760 KB Output is correct
25 Correct 2784 ms 39484 KB Output is correct
26 Correct 3768 ms 45228 KB Output is correct
27 Correct 3767 ms 44520 KB Output is correct
28 Correct 1164 ms 15184 KB Output is correct
29 Correct 1006 ms 14368 KB Output is correct
30 Correct 1167 ms 15072 KB Output is correct
31 Correct 1065 ms 14420 KB Output is correct
32 Correct 4629 ms 44708 KB Output is correct
33 Correct 2064 ms 36412 KB Output is correct
34 Correct 3380 ms 45140 KB Output is correct
35 Correct 1016 ms 36696 KB Output is correct
36 Correct 128 ms 19536 KB Output is correct
37 Correct 1931 ms 36692 KB Output is correct
38 Execution timed out 9037 ms 43808 KB Time limit exceeded
39 Halted 0 ms 0 KB -