oj.uz

Submission #666741

# Submission time Handle Problem Language Result Execution time Memory
666741 2022-11-29T13:44:52 Z 1bin Dancing Elephants (IOI11_elephants) C++14
50 / 100
 745 ms 5136 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[0].emplace_back(X[i], i);
    }
    sort(all(v[0]));
    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);
    
    //cout << "turns is " << q << '\n';
    //for(auto&[x, ix] : v[0]) cout << x <<  ' ';
    //cout << '\n';
    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];
            //cout << ix << ' ' << cnt[ix] << ' ' << d[ix] << '\n';
        }
    }
    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 'void go(int)':
elephants.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto&[x, ix] = v[k][i];
      |              ^
elephants.cpp: In function 'int find(int)':
elephants.cpp:58:74: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |         if(v[i].size() && (v[i][0].first < X[x] || v[i][0].first == X[x] && v[i][0].second <= X[x])) ret = i;
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:82:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |             auto&[x, ix] = *it;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 0 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 0 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 425 ms 1692 KB Output is correct
8 Correct 447 ms 3016 KB Output is correct
9 Correct 556 ms 5136 KB Output is correct
10 Correct 556 ms 4932 KB Output is correct
11 Correct 558 ms 4804 KB Output is correct
12 Correct 745 ms 4956 KB Output is correct
13 Correct 580 ms 4668 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 0 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 425 ms 1692 KB Output is correct
8 Correct 447 ms 3016 KB Output is correct
9 Correct 556 ms 5136 KB Output is correct
10 Correct 556 ms 4932 KB Output is correct
11 Correct 558 ms 4804 KB Output is correct
12 Correct 745 ms 4956 KB Output is correct
13 Correct 580 ms 4668 KB Output is correct
14 Incorrect 166 ms 3668 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 0 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 425 ms 1692 KB Output is correct
8 Correct 447 ms 3016 KB Output is correct
9 Correct 556 ms 5136 KB Output is correct
10 Correct 556 ms 4932 KB Output is correct
11 Correct 558 ms 4804 KB Output is correct
12 Correct 745 ms 4956 KB Output is correct
13 Correct 580 ms 4668 KB Output is correct
14 Incorrect 166 ms 3668 KB Output isn't correct
15 Halted 0 ms 0 KB -