oj.uz

답안 #1085148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085148 2024-09-07T15:51:14 Z Wansur 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 23784 KB 
#include <bits/stdc++.h>
#define ent '\n'

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

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

void calc(vector<int> &c){
    for(int _=(int)c.size()-1;_>=0;_--){
        int i = c[_];
        assert(_ == 0 || a[i] >= a[c[_ - 1]]);
        if(a[c.back()] > a[i] + l){
            int pos = 0;
            for(int L = 0, R = (int)c.size() - 1; L <= R;){
                int mid = L + R >> 1;
                if(a[c[mid]] > a[i] + l){
                    pos = mid;
                    R = mid - 1;
                }
                else L = mid + 1;
            }
            out[i] = out[c[pos]];
            dp[i] = dp[c[pos]] + 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 = 500;
    for(int i=0;i<n;i++){
        a[i] = X[i];
    }
    sort(a, a+n);
    for(int i=0;i<n;i++){
        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){
    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){
    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 calc(std::vector<int>&)':
elephants.cpp:20:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |                 int mid = L + R >> 1;
      |                           ~~^~~
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:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:92:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:94:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         while(g[bl].size() > k / 2){
      |               ~~~~~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1039 ms 7540 KB Output is correct
8 Correct 1018 ms 8256 KB Output is correct
9 Correct 1238 ms 10844 KB Output is correct
10 Correct 675 ms 10840 KB Output is correct
11 Correct 671 ms 10836 KB Output is correct
12 Correct 1266 ms 10832 KB Output is correct
13 Correct 1296 ms 10836 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1039 ms 7540 KB Output is correct
8 Correct 1018 ms 8256 KB Output is correct
9 Correct 1238 ms 10844 KB Output is correct
10 Correct 675 ms 10840 KB Output is correct
11 Correct 671 ms 10836 KB Output is correct
12 Correct 1266 ms 10832 KB Output is correct
13 Correct 1296 ms 10836 KB Output is correct
14 Correct 789 ms 8944 KB Output is correct
15 Correct 912 ms 9040 KB Output is correct
16 Correct 1761 ms 11356 KB Output is correct
17 Correct 2159 ms 13324 KB Output is correct
18 Correct 2288 ms 12892 KB Output is correct
19 Correct 2973 ms 13392 KB Output is correct
20 Correct 2215 ms 13136 KB Output is correct
21 Correct 2235 ms 13124 KB Output is correct
22 Correct 2423 ms 12880 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1039 ms 7540 KB Output is correct
8 Correct 1018 ms 8256 KB Output is correct
9 Correct 1238 ms 10844 KB Output is correct
10 Correct 675 ms 10840 KB Output is correct
11 Correct 671 ms 10836 KB Output is correct
12 Correct 1266 ms 10832 KB Output is correct
13 Correct 1296 ms 10836 KB Output is correct
14 Correct 789 ms 8944 KB Output is correct
15 Correct 912 ms 9040 KB Output is correct
16 Correct 1761 ms 11356 KB Output is correct
17 Correct 2159 ms 13324 KB Output is correct
18 Correct 2288 ms 12892 KB Output is correct
19 Correct 2973 ms 13392 KB Output is correct
20 Correct 2215 ms 13136 KB Output is correct
21 Correct 2235 ms 13124 KB Output is correct
22 Correct 2423 ms 12880 KB Output is correct
23 Correct 6374 ms 22464 KB Output is correct
24 Correct 8146 ms 22608 KB Output is correct
25 Correct 5963 ms 22532 KB Output is correct
26 Execution timed out 9009 ms 23784 KB Time limit exceeded
27 Halted 0 ms 0 KB -