oj.uz

Submission #666753

# Submission time Handle Problem Language Result Execution time Memory
666753 2022-11-29T14:03:32 Z 1bin Dancing Elephants (IOI11_elephants) C++14
26 / 100
 15 ms 1304 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[b][b * 2 + 5], d[b][b * 2 + 5];
vector<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]);
    }
    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 = v[k][i];
        while(v[k][ii - 1] - x > l) ii--;
        if(ii == sz){
            cnt[k][i] = 1; 
            d[k][i] = x + l;
        }
        else {
            cnt[k][i] = cnt[k][ii] + 1;
            d[k][i] = d[k][ii];
        }
    }
    return;
}
 
void build(){
    vector<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] <= x) ret = i;
    return ret;
}
 
int update(int i, int y){
    if(q++ % b == 0) build();
    int k = find(X[i]);
    v[k].erase(lower_bound(all(v[k]), X[i]));
    go(k);
    
    X[i] = y;
    k = find(X[i]);
    auto it = lower_bound(all(v[k]), X[i]);
    if(it == v[k].end()) v[k].emplace_back(X[i]);
    else v[k].insert(it, X[i]);
    go(k);

    int ans = 0, e = -1;
    for(int i = 0; i < b; i++){
        auto it = upper_bound(all(v[i]), e);
        if(it != v[i].end()){
            int ix = it - v[i].begin();
            ans += cnt[k][ix]; e = d[k][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;
}
*/

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 1 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 1 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
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 1 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 Incorrect 15 ms 1304 KB Output isn't correct
8 Halted 0 ms 0 KB -

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 1 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 Incorrect 15 ms 1304 KB Output isn't correct
8 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 1 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 Incorrect 15 ms 1304 KB Output isn't correct
8 Halted 0 ms 0 KB -