oj.uz

Submission #666745

# Submission time Handle Problem Language Result Execution time Memory
666745 2022-11-29T13:50:02 Z 1bin Dancing Elephants (IOI11_elephants) C++17
50 / 100
 725 ms 3296 KB 
#include <bits/stdc++.h>
#include "elephants.h"
 
using namespace std;
 
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
const int b = 400;
int n, l, m, X[NMAX], q, cnt[NMAX], d[NMAX];
vector<pair<int, int>> v[b];
 
void init(int n_, int l_, int X_[]){
    n = n_; l = l_;
    for(int i = 0; i < n; i++) {
        X[i] = X_[i];
        v[i/b].emplace_back(X[i], i);
    }
    return;
}
 
void go(int k){
    if(v[k].empty()) return;
    int sz = v[k].size();
    int ii = sz;
    
    for(int i = sz - 1; i >= 0; i--){
        auto&[x, ix] = v[k][i];
        while(v[k][ii - 1].first - x > l) ii--;
        if(ii == sz){
            cnt[ix] = 1; 
            d[ix] = x + l;
        }
        else {
            int p = v[k][ii].second;
            cnt[ix] = cnt[p] + 1;
            d[ix] = d[p];
        }
    }
    return;
}
 
void build(){
    vector<pair<int, int>> t;
    for(int i = 0; i < b; i++){
        for(auto& p : v[i]) t.emplace_back(p);
        v[i].clear();
    }
    for(int i = 0; i < n; i++) v[i / b].emplace_back(t[i]);
    for(int i = 0; i < b; i++) go(i);
    return;
}
 
int find(int x){
    int ret = 0;
    for(int i = 0; i < b; i++)
        if(v[i].size() && (v[i][0].first < X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x])) ret = i;
    return ret;
}
 
int update(int i, int y){
    if(q++ % b == 0) build();
    int k = find(i);
    v[k].erase(lower_bound(all(v[k]), make_pair(X[i], i)));
    go(k);
    
    X[i] = y;
    k = find(i);
    auto it = lower_bound(all(v[k]), make_pair(X[i], i));
    if(it == v[k].end()) v[k].emplace_back(X[i], i);
    else v[k].insert(it, {X[i], i});
    go(k);

    int ans = 0, e = -2;
    for(int i = 0; i < b; i++){
        auto it = lower_bound(all(v[i]), make_pair(e + 1, 0));
        if(it != v[i].end()){
            auto&[x, ix] = *it;
            ans += cnt[ix]; e = d[ix];
        }
    }
    return ans;
}
 
/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> l >> m;
    for(int i = 0; i < n; i++) cin >> X[i];
    init(n, l, X);
    while(m--){
        int i, y;
        cin >> i >> y;
        cout << update(i, y) << '\n';
    }
    return 0;
}
*/

Compilation message

elephants.cpp: In function 'int find(int)':
elephants.cpp:57:74: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   57 |         if(v[i].size() && (v[i][0].first < X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x])) ret = i;

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 433 ms 1532 KB Output is correct
8 Correct 432 ms 1772 KB Output is correct
9 Correct 546 ms 3148 KB Output is correct
10 Correct 531 ms 3124 KB Output is correct
11 Correct 532 ms 3296 KB Output is correct
12 Correct 725 ms 3132 KB Output is correct
13 Correct 562 ms 3204 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 433 ms 1532 KB Output is correct
8 Correct 432 ms 1772 KB Output is correct
9 Correct 546 ms 3148 KB Output is correct
10 Correct 531 ms 3124 KB Output is correct
11 Correct 532 ms 3296 KB Output is correct
12 Correct 725 ms 3132 KB Output is correct
13 Correct 562 ms 3204 KB Output is correct
14 Incorrect 162 ms 2028 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 433 ms 1532 KB Output is correct
8 Correct 432 ms 1772 KB Output is correct
9 Correct 546 ms 3148 KB Output is correct
10 Correct 531 ms 3124 KB Output is correct
11 Correct 532 ms 3296 KB Output is correct
12 Correct 725 ms 3132 KB Output is correct
13 Correct 562 ms 3204 KB Output is correct
14 Incorrect 162 ms 2028 KB Output isn't correct
15 Halted 0 ms 0 KB -