oj.uz

Submission #1085190

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

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

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 = 909;
    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:53:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if(g[last].size() >= k){
      |            ~~~~~~~~~~~~~~~^~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int _=0;_<g[block[i]].size();_++){
      |                     ~^~~~~~~~~~~~~~~~~~~
elephants.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:117:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:119:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |         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 4 ms 5136 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 4 ms 5136 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5148 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 4 ms 5136 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5148 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2192 ms 10764 KB Output is correct
8 Correct 2342 ms 11648 KB Output is correct
9 Correct 2709 ms 16352 KB Output is correct
10 Correct 1179 ms 18004 KB Output is correct
11 Correct 1235 ms 18052 KB Output is correct
12 Correct 2329 ms 17744 KB Output is correct
13 Correct 1464 ms 17844 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 4 ms 5136 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5148 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2192 ms 10764 KB Output is correct
8 Correct 2342 ms 11648 KB Output is correct
9 Correct 2709 ms 16352 KB Output is correct
10 Correct 1179 ms 18004 KB Output is correct
11 Correct 1235 ms 18052 KB Output is correct
12 Correct 2329 ms 17744 KB Output is correct
13 Correct 1464 ms 17844 KB Output is correct
14 Correct 957 ms 11980 KB Output is correct
15 Correct 1816 ms 14340 KB Output is correct
16 Correct 2368 ms 18300 KB Output is correct
17 Correct 2753 ms 22384 KB Output is correct
18 Correct 3661 ms 22100 KB Output is correct
19 Correct 4277 ms 22868 KB Output is correct
20 Correct 2990 ms 22872 KB Output is correct
21 Correct 3549 ms 22872 KB Output is correct
22 Correct 2404 ms 23056 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 4 ms 5136 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5148 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2192 ms 10764 KB Output is correct
8 Correct 2342 ms 11648 KB Output is correct
9 Correct 2709 ms 16352 KB Output is correct
10 Correct 1179 ms 18004 KB Output is correct
11 Correct 1235 ms 18052 KB Output is correct
12 Correct 2329 ms 17744 KB Output is correct
13 Correct 1464 ms 17844 KB Output is correct
14 Correct 957 ms 11980 KB Output is correct
15 Correct 1816 ms 14340 KB Output is correct
16 Correct 2368 ms 18300 KB Output is correct
17 Correct 2753 ms 22384 KB Output is correct
18 Correct 3661 ms 22100 KB Output is correct
19 Correct 4277 ms 22868 KB Output is correct
20 Correct 2990 ms 22872 KB Output is correct
21 Correct 3549 ms 22872 KB Output is correct
22 Correct 2404 ms 23056 KB Output is correct
23 Execution timed out 9021 ms 39076 KB Time limit exceeded
24 Halted 0 ms 0 KB -