oj.uz

Submission #1085187

# Submission time Handle Problem Language Result Execution time Memory
1085187 2024-09-07T16:41:33 Z Wansur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 40236 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 = 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;
    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 4952 KB Output is correct
2 Correct 3 ms 4952 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 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 1979 ms 10732 KB Output is correct
8 Correct 1905 ms 11828 KB Output is correct
9 Correct 2342 ms 16352 KB Output is correct
10 Correct 1033 ms 18256 KB Output is correct
11 Correct 1144 ms 18004 KB Output is correct
12 Correct 2119 ms 18004 KB Output is correct
13 Correct 1459 ms 18004 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 1979 ms 10732 KB Output is correct
8 Correct 1905 ms 11828 KB Output is correct
9 Correct 2342 ms 16352 KB Output is correct
10 Correct 1033 ms 18256 KB Output is correct
11 Correct 1144 ms 18004 KB Output is correct
12 Correct 2119 ms 18004 KB Output is correct
13 Correct 1459 ms 18004 KB Output is correct
14 Correct 886 ms 12280 KB Output is correct
15 Correct 1630 ms 14376 KB Output is correct
16 Correct 2071 ms 18804 KB Output is correct
17 Correct 2498 ms 22352 KB Output is correct
18 Correct 3396 ms 22360 KB Output is correct
19 Correct 4262 ms 23292 KB Output is correct
20 Correct 2766 ms 22856 KB Output is correct
21 Correct 3227 ms 22736 KB Output is correct
22 Correct 2338 ms 23148 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 1979 ms 10732 KB Output is correct
8 Correct 1905 ms 11828 KB Output is correct
9 Correct 2342 ms 16352 KB Output is correct
10 Correct 1033 ms 18256 KB Output is correct
11 Correct 1144 ms 18004 KB Output is correct
12 Correct 2119 ms 18004 KB Output is correct
13 Correct 1459 ms 18004 KB Output is correct
14 Correct 886 ms 12280 KB Output is correct
15 Correct 1630 ms 14376 KB Output is correct
16 Correct 2071 ms 18804 KB Output is correct
17 Correct 2498 ms 22352 KB Output is correct
18 Correct 3396 ms 22360 KB Output is correct
19 Correct 4262 ms 23292 KB Output is correct
20 Correct 2766 ms 22856 KB Output is correct
21 Correct 3227 ms 22736 KB Output is correct
22 Correct 2338 ms 23148 KB Output is correct
23 Execution timed out 9008 ms 40236 KB Time limit exceeded
24 Halted 0 ms 0 KB -